16
\$\begingroup\$

This is a puzzle, the cops' thread can be found here.

Your task will be to find an anagram of the provided programs in the cops' thread that performs its left inverse.

Once you crack an answer post the solution as an answer below and notify the original answerer.

You will be scored on the number of programs you are the first to crack.

\$\endgroup\$

15 Answers 15

21
\$\begingroup\$

Python 3, 46 bytes, Lynn

lambda x0223334566789:(x0223334566789*89)//178
\$\endgroup\$
  • \$\begingroup\$ How do I "notify the original answerer"? \$\endgroup\$ – G B Jan 16 '17 at 15:24
  • \$\begingroup\$ Left a comment linking your answer on the original \$\endgroup\$ – Sefa Jan 16 '17 at 15:25
  • \$\begingroup\$ You should drop the f= at the start of your code since its not needed and not part of the original function \$\endgroup\$ – 0 ' Jan 16 '17 at 15:26
  • \$\begingroup\$ Done, I just copy-pasted it too quickly. \$\endgroup\$ – G B Jan 16 '17 at 15:26
  • 16
    \$\begingroup\$ Here I am actually brute forcing a solution (and even assuming one exists) and you just sidestep the entire problem! +1 \$\endgroup\$ – orlp Jan 16 '17 at 15:26
14
\$\begingroup\$

Python 2, 225 bytes, orlp

p=90930641353124136621573325641513715557077985927835294018496194596645372722158;q=101979812089012306249375934082966806799688507587087308196267706260111970225882#--223444799
lambda n:pow(n,pow(65537,(p*q-2*(p+q))/4,p*q),~p*~q)

Guess I got lucky after guessing random prime divisors all day...

(Default c4.8xlarge spot limit is 4, but I managed to bump it to 10 last year. Had to tweak the FAAS config from 16 slaves to 6 though (+3 mpi, 1 master). 20m polyselect, 12h 50m sieving, 2h 25m linalg, 30m sqrt. Total cost ~$70. At least @orlp was nice enough to pick a solvable size, but I'm not doing this again! Thanks to @IlmariKaronen for the last step, and yes I'm joking about the guessing :P)

\$\endgroup\$
  • \$\begingroup\$ I.. what... Now I feel bad for costing you money :( I intentionally picked a size that would still be reasonably small but too high a cost to attack. I didn't actually think anyone would spend money on this. \$\endgroup\$ – orlp Jan 22 '17 at 9:37
  • 1
    \$\begingroup\$ @orlp Totally worth it as a one-off experience for me. I hope people learn something about 512-bit RSA security in the wild from this :) \$\endgroup\$ – Sp3000 Jan 22 '17 at 9:51
  • \$\begingroup\$ This is real dedication to golfing, spending not only time but money! Interesting to note that an attacker could potentially break 512-bit RSA for free via cloud compute service trials. \$\endgroup\$ – miles Jan 22 '17 at 12:53
  • \$\begingroup\$ @miles I should mention that AWS has credit for students if anyone wants to try, and I wouldn't be surprised if other services did the same. Hence you're probably not far off with that trials idea, at least for the first time. (If anyone wants to try though - make sure you delete all volumes, AMIs, etc. once you're done because otherwise you'll be charged for storage) \$\endgroup\$ – Sp3000 Jan 22 '17 at 13:06
11
\$\begingroup\$

Python 2, 83 bytes, orlp

Original:

#((()))****+,,---/2289;==oppppppqqqqqw~~
lambda n:pow(n,65537,10998167423251438693)

Crack:

p=3207399658;q=3428998126#--11
lambda n:pow(n,pow(65537,(p*q-2*(p+q))/4,p*q),~p*~q)

Try it online!

RSA cracking done by Wolfram Alpha. ;)

\$\endgroup\$
  • \$\begingroup\$ I just realized ~p*~q is straight up shorter than -~p*-~q, oops. \$\endgroup\$ – orlp Jan 16 '17 at 19:02
  • \$\begingroup\$ How did you reverse engineer the (p*q-2*(p+q))/4 part though? :) \$\endgroup\$ – orlp Jan 16 '17 at 19:03
  • \$\begingroup\$ That was the trickiest part, wasn't it? Basically, knowledge of the Carmichael function and the fact that p/2 and q/2 were both odd primes, and a bunch of trial and error to find something that would work using the available characters. \$\endgroup\$ – Ilmari Karonen Jan 16 '17 at 19:27
  • \$\begingroup\$ I intentionally chose p and q (the real ones, the one in the code are p-1 and q-1 for golfing purposes) such that (p-1)/2 is prime so that we have φ(φ(pq)) = ((p-1)/2-1)((q-1)/2-1). This allows us to compute the modular inverse of 65537 mod φ(pq) (what we need for RSA) using Euler's identity, making the answer a lot shorter because we don't need to implement modular inverse logic or hardcode another large constant. Apart from the -~q*-~p -> ~q*~p, you found exactly my function :) \$\endgroup\$ – orlp Jan 16 '17 at 20:08
  • 1
    \$\begingroup\$ Actually, to pick a minor nit, I believe φ(φ(pq)) = 2((p-1)/2-1)((q-1)/2-1) for safe primes p and q, because φ(4) = 2. But λ(φ(pq)) = lcm(2, (p-1)/2-1, (q-1)/2-1) is at most ((p-1)/2-1)((q-1)/2-1)/2, and any multiple of that, minus one, will do for the exponent. :) \$\endgroup\$ – Ilmari Karonen Jan 16 '17 at 20:22
7
\$\begingroup\$

Python 3, 80 bytes, Wolfram

from bisect import*
q=int(input())
print(bisect([(h+1)**2 for h in range(q)],q))

This was really hard to crack! I use the bisect library, which is included in the Python 3 distribution. The bisect function takes a sorted list and an element, and returns the rightmost index where the element could be inserted to maintain order. We just give it the length-q list of squares starting from 1 and the element q.

\$\endgroup\$
  • 1
    \$\begingroup\$ I was going to suggest changing (h+1) to -~h. Then I realized that that's not the point of this challenge :P \$\endgroup\$ – ETHproductions Jan 20 '17 at 20:15
  • \$\begingroup\$ @ETHproductions That'd be incorrect anyway due to operator precedence. \$\endgroup\$ – Sp3000 Jan 21 '17 at 8:19
  • \$\begingroup\$ @Sp3000 Huh, I had no idea that ** has higher precedence than ~ in Python. I suppose that's better than in JS, where -~2**2 throws a syntax error ("unparenthesized unary expression can't appear on the left-hand side of '**'"). \$\endgroup\$ – ETHproductions Jan 21 '17 at 15:42
  • \$\begingroup\$ @ETHproductions They actually did that to avoid ambiguities, which, as I might add, is very uncharacteristic of most JS design. \$\endgroup\$ – Esolanging Fruit Jul 15 '17 at 9:27
  • \$\begingroup\$ @Challenger5 Actually, I'd have to disagree with you there: in recent years TC39 has been extremely careful to make sure any new features added are as completely free of ambiguities as possible (which includes the ** operator, added in ES2017) \$\endgroup\$ – ETHproductions Jul 15 '17 at 12:20
6
\$\begingroup\$

Javascript, 21 bytes, Arnauld

Original

b=>Math.pow(b,torc=3)

Crack

o=>Math.cbrt(o,pbw=3)

Returns the cube root.

\$\endgroup\$
  • \$\begingroup\$ There you go! ;) \$\endgroup\$ – Arnauld Jan 16 '17 at 16:16
  • \$\begingroup\$ @Arnauld: I find it a bit weird that JS allows you to call functions with more arguments than they're defined for. I wonder what the thought behind that is. \$\endgroup\$ – Emigna Jan 16 '17 at 16:45
  • 6
    \$\begingroup\$ You're right, JS allows that by design. Extra arguments are not completely lost, though, since they're stored in the arguments object which may be manually accessed by the function. \$\endgroup\$ – Arnauld Jan 16 '17 at 16:51
5
\$\begingroup\$

7, 9 bytes, ais523

00000000: 0173 dc25 7e13 dcb6 1f                   .s.%~....

Because brute force always wins, and 9! is only 362880

\$\endgroup\$
4
\$\begingroup\$

Processing.js, 59 bytes, Kritixi Lithos

Original:

float igetuwebaoli(int p){return p*(((17*-4*-3)))+0+0;}//,,

Crack:

int loabewuteg(float p,i){return (i+0**+0,(p/17/(-4*-3)));}

Well, that was easy enough. The hardest part was figuring out where to stick the extra commas and asterisks. Fortunately, it seems that Processing allows extra unused function parameters as well as C-style comma expressions.

\$\endgroup\$
  • 1
    \$\begingroup\$ Apparently, the interpreter I linked was wrong. In fact, most (or even all) online interpreters are probably going to be wrong since Processing-java gets pre-compiled to Processing.js. Right now, I think the best course of action would be for me and you to change our answers to "Processing.js" instead of Processing because then your answer would be valid (Processing-java gives tons of errors). I will post a separate answer with the same code as Processing-java, but for this the nest interpreter would be to install it from processing.org. Well done anyways! \$\endgroup\$ – Cows quack Jan 17 '17 at 5:55
4
\$\begingroup\$

JavaScript (ES6), 63 bytes, SLuck49

Original:

x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`)

Crack:

x=>eval(atob`CgpNYXRoLnBvdyh4LTEsMC41KSAvLw4589CEIKKMRefipyz=`)

The base64 code above decodes to:



Math.pow(x-1,0.5) //...

where the ... stands for a bunch of random garbage that is ignored by the JS interpreter, since it's in a comment.

I found this solution by trial and error. In the end, the only really tricky part were the two newlines at the beginning of the code, needed to make the rest line up properly and to get the M in Math to base64-encode into something that was available in the original character set. I first tried spaces, but " M" base64-encodes into "ICBN" and I needed the only available B to encode ".po" later in the code. "0+M", "1*M", "1?M" or any other similar no-op prefixes I could think of didn't work either, but newlines did.

I suspect this may not be exactly the intended solution, but whatever — it works. :)

Demo:

var f = x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`)
var g = x=>eval(atob`CgpNYXRoLnBvdyh4LTEsMC41KSAvLw4589CEIKKMRefipyz=`)
for (var i = -0; i <= 10; i++) console.log(i, '->', f(i), '->', g(f(i)))

\$\endgroup\$
  • \$\begingroup\$ Good job finding something that worked, I had hoped putting the extra characters at the start would make this a little harder \$\endgroup\$ – SLuck49 Jan 18 '17 at 13:38
  • \$\begingroup\$ Impressive :) I took the exact same approach but didn't think to try newline. I was trying to lose a C elsewhere but was getting nowhere. \$\endgroup\$ – Chris M Jan 18 '17 at 19:34
3
\$\begingroup\$

Brain-Flak, 26 bytes, Wheat Wizard

Original (adds 13)

((((()()())){}[()]){}{}{})

Crack (subtracts 13)

([(((()())()){}){}{}](){})
\$\endgroup\$
3
\$\begingroup\$

J, 8 bytes, miles

[:]-:[+:

Simple swapping of +: for -: (double for halve).

\$\endgroup\$
  • \$\begingroup\$ Also you can swap the left and right verbs: [:[+:]-:. \$\endgroup\$ – randomra Jan 19 '17 at 21:26
3
\$\begingroup\$

Javascript, 15 bytes, insertusernamehere

Original

t=>(!!0+~~t+~0)

Crack

t=>(~~!!~0+t+0)
\$\endgroup\$
3
\$\begingroup\$

Python 2, 47 bytes, Wheat Wizard

lambda x:sorted(a**2for a in range(x)).index(x)
\$\endgroup\$
  • \$\begingroup\$ Good job! You found the exact solution I had in mind \$\endgroup\$ – Sriotchilism O'Zaic Jan 19 '17 at 20:34
3
\$\begingroup\$

JavaScript (ES6), 46 bytes, SLuck49

Original (calculates ln(x+1))

x=>Math.log(x+(+String(t=985921996597669)[5]))

Crack

x=>Math[(lg=19979699+55686).toString(9+25)](x)

I never would have cracked this if I hadn't realized that the inverse is a Math built-in. (lg=19979699+55686).toString(9+25) is just a convoluted way of returning "expm1".

\$\endgroup\$
  • \$\begingroup\$ Nicely done! Yeah I was looking through the functions on Math to decide what to use, saw expm1, and said "Wait, that's a thing?" \$\endgroup\$ – SLuck49 Jan 20 '17 at 15:34
2
\$\begingroup\$

J, 10 bytes, miles

1%:@*~>:[<

I have to write something here because the answer is too short.

\$\endgroup\$
2
\$\begingroup\$

J, 29 bytes, Zgarb

Original

5#.[:,(3 5&#:(-$]-)7)#.inv"0]

Crack

[:(](07-5)"3 #.-:&#$,)5#.inv]

Try it online!

Another crack equivalent is

[:((3 ]7-5)#.-:&#$,)5#.inv"0]

Explanation

[:(](07-5)"3 #.-:&#$,)5#.inv]  Input: integer n
                            ]  Get n
                      5        The constant 5
                       #.inv   Get the digits of n in base 5
[:(                  )         Operate on those digits D
                    ,            Flatten D (does nothing since it is already a list)
                  #              Get the length of D
               -:&               Halve it
                   $             Reshape D to half its length (only the base 2 digits)
    (07-5)"3                     The constant 2 with rank 3
             #.                  Convert the front-half of D to a decimal from base 2
   ]                             Return the right result
\$\endgroup\$
  • \$\begingroup\$ Yep, that works! It's a bit different from my solution, but there's a lot of leeway. The basic logic is the same though. \$\endgroup\$ – Zgarb Jan 23 '17 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.