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\$
0

15 Answers 15

21
\$\begingroup\$

Python 3, 46 bytes, Lynn

lambda x0223334566789:(x0223334566789*89)//178
\$\endgroup\$
8
  • \$\begingroup\$ How do I "notify the original answerer"? \$\endgroup\$
    – G B
    Jan 16, 2017 at 15:24
  • \$\begingroup\$ Left a comment linking your answer on the original \$\endgroup\$
    – Sefa
    Jan 16, 2017 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, 2017 at 15:26
  • \$\begingroup\$ Done, I just copy-pasted it too quickly. \$\endgroup\$
    – G B
    Jan 16, 2017 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, 2017 at 15:26
15
\$\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\$
4
  • \$\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, 2017 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, 2017 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, 2017 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, 2017 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\$
7
  • \$\begingroup\$ I just realized ~p*~q is straight up shorter than -~p*-~q, oops. \$\endgroup\$
    – orlp
    Jan 16, 2017 at 19:02
  • \$\begingroup\$ How did you reverse engineer the (p*q-2*(p+q))/4 part though? :) \$\endgroup\$
    – orlp
    Jan 16, 2017 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\$ Jan 16, 2017 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, 2017 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\$ Jan 16, 2017 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\$
6
  • 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\$ Jan 20, 2017 at 20:15
  • \$\begingroup\$ @ETHproductions That'd be incorrect anyway due to operator precedence. \$\endgroup\$
    – Sp3000
    Jan 21, 2017 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\$ Jan 21, 2017 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\$ Jul 15, 2017 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\$ Jul 15, 2017 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\$
3
  • \$\begingroup\$ There you go! ;) \$\endgroup\$
    – Arnauld
    Jan 16, 2017 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, 2017 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, 2017 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
  • 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\$
    – user41805
    Jan 17, 2017 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\$
2
  • \$\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, 2017 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, 2017 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\$
1
  • \$\begingroup\$ Also you can swap the left and right verbs: [:[+:]-:. \$\endgroup\$
    – randomra
    Jan 19, 2017 at 21:26
3
\$\begingroup\$

Javascript, 15 bytes, insertusernamehere

Original

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

Crack

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

Python 2, 47 bytes, Wheat Wizard

lambda x:sorted(a**2for a in range(x)).index(x)
\$\endgroup\$
1
  • \$\begingroup\$ Good job! You found the exact solution I had in mind \$\endgroup\$
    – Wheat Wizard
    Jan 19, 2017 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\$
1
  • \$\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, 2017 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\$
1
  • \$\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, 2017 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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