Codebreakers and Codewriters

18

6

Let's say you have some text, and you want it to send it to your friend, but you don't want anyone else to read it. That probably means you want to encrypt it so that only you and your friend can read it. But, there is a problem: you and your friend forgot to agree on an encryption method, so if you send them a message, they won't be able to decrypt it!

After thinking about this for a while, you decide to just send your friend the code to encrypt your message along with the message. Your friend is very smart, so they can probably figure out how to decrypt the message by studying the encryption method.

Of course, since other people might be reading the message, you want to choose an encryption scheme that makes it as hard as possible to crack (figure out the decryption scheme).

Cops' Task

In this challenge, Cops will play the role of the writer: you will design an encryption scheme that converts strings to strings. However, this encryption scheme must be bijective, meaning that no two strings must map to another string, and every string can be mapped to by an input. It must take only one input—the string to be encoded.

You will then post some code that performs the encryption, and a single message encrypted with the scheme detailed by your code.

Since you are paying by the byte to send messages, your score will be the length of your code plus the length of the ciphertext. If your answer is cracked, you will have a score of infinity.

After one week, you may reveal the text and mark your answer as Safe. Safe answers are those that cannot be cracked.

Robbers' Task

Robbers will play either as the friend of the writer or the malicious middle man (there is no material difference, but you can role-play as either if it makes it more fun to do so). They will take the encryption schemes and the ciphertext and attempt to figure out the encrypted message. Once they figure out the encrypted message, they will post it in a comment. (There will not be a separate robbers' thread for this question.)

The winner will be the robber with the most cracks.


Here is an example of what a cracked solution might look like:

Buy More Oranges

Post Rock Garf Hunter

Posted 2017-07-19T18:12:43.117

Reputation: 55 382

If the encoding is bijective, what are the domain and codomain? – Leaky Nun – 2017-07-19T18:21:35.453

The strings with which characters? – Leaky Nun – 2017-07-19T18:22:49.430

1@WheatWizard Which 256? You mean 256 bytes not characters right? – Erik the Outgolfer – 2017-07-19T18:34:06.907

7What's to stop somebody from using a cryptographically secure function? – Tutleman – 2017-07-19T18:49:45.120

Related challenge: All your bijective base are belong to us

– Ilmari Karonen – 2017-07-19T19:26:55.907

2On who is the burden of proving bijectivity: the cop or potential robbers? I.e., if it is unknown if a function is bijective, what happens? – Stephen – 2017-07-19T19:28:27.480

@WheatWizard "I don't know of any function that is cryptographically secure when the key is given" without this you'd be practically left with no security. Practically all security rely on the fact that it is still secure when you know the algorithm. Look up RSA encryption. – Leaky Nun – 2017-07-19T19:39:19.520

@WheatWizard How is RSA not bijective? – Leaky Nun – 2017-07-19T19:51:03.050

@WheatWizard with one key there is only one encryption. – Leaky Nun – 2017-07-19T20:16:29.317

@WheatWizard I didn't use padding in my implementation. – Leaky Nun – 2017-07-19T20:33:18.130

So the trick here is, write a program in Malbolge. – KSmarts – 2017-07-20T15:04:17.393

Answers

5

Jelly, 57 + 32 = 89 bytes (cracked)

“¡ḟċ⁷Ḣṡ⁵ĊnɠñḂƇLƒg⁺QfȥẒṾ⁹+=?JṚWġ%Aȧ’
O‘ḅ256b¢*21%¢ḅ¢ḃ256’Ọ

Encrypted message:

EªæBsÊ$ʳ¢?r×­Q4e²?ò[Ý6

As a hex-string:

4518AAE6421973CA
9724CAB3A23F72D7
AD18855134651810
B23F1CF25BDD9036

Explanation:

O‘ḅ256b¢*21%¢ḅ¢ḃ256’Ọ
O                     convert each into codepoint
 ‘ḅ256                convert from bijective base 256 to integer
      b¢              convert from integer to base N
        *21           map each to its 21th power
           %¢         modulo N
             ḅ¢       convert to integer from base N
               ḃ256’  convert from integer to bijective base 256
                    Ọ convert each from codepoint

Where N is encoded by the string “¡ḟċ⁷Ḣṡ⁵ĊnɠñḂƇLƒg⁺QfȥẒṾ⁹+=?JṚWġ%Aȧ’, which is the number 105587021056759938494595233483151378724567978408381355454441180598980268016731.

Also, this is the RSA method with N given above and public key 21. Cracking this is equivalent to finding the two prime factors of N.

Leaky Nun

Posted 2017-07-19T18:12:43.117

Reputation: 45 011

Well. I'm able to decrypt my own encrypted message with the key I've found, but it seems to fail with yours. :-/ (The expected result is not a 4-character non-English message, is it?) – Arnauld – 2017-07-19T22:18:43.177

3

The message is _ìNb (Try it online!).

– Anders Kaseorg – 2017-07-19T22:23:33.423

@AndersKaseorg Yup. That's what I had, but I was expecting something slightly more meaningful. :-) – Arnauld – 2017-07-19T22:25:56.837

1

For what it's worth, here is the code I used on my side.

– Arnauld – 2017-07-19T22:42:02.607

(where N was factorized with PPSIQS by Satoshi Tomabechi) – Arnauld – 2017-07-19T22:52:17.203

Ah, gotcha. I've been running a program I wrote to factor N for a few hours with no luck...I didn't do out the math before I killed it, but I think it would have taken several months – musicman523 – 2017-07-20T04:11:24.057

@musicman523 Actually... it only takes 6 minutes to factor a 256-bit integer even if I chose the primes correctly. brb increasing the number of bits. – Leaky Nun – 2017-07-20T04:43:26.787

1

@AndersKaseorg Jelly attempts to eval it's arguments, so null bytes are indeed possible. https://tio.run/##y0rNyan8/9//////6jEGIKgOAA

– Dennis – 2017-07-20T05:43:30.160

@LeakyNun the crap program I wrote was far from optimal...I was just hoping you chose two numbers really close together – musicman523 – 2017-07-20T18:15:57.133

5

Jelly, 88 + 64 = 152 bytes

Encryption function:

“¥@ɦ⁺€€Ṅ`yȤDƁWĊ;Y^y⁻U ⁸ßɠƁXẹṡWZc'µ÷ḷỊ0ÇtṙA×Ḃß4©qV)iḷỊDƭ Mṛ+<ṛ_idðD’
O‘ḅ256b¢*21%¢ḅ¢ḃ256’Ọ

Encrypted message:

AX!?ÖÍL¹    JÓ°û0àah4Û{µÌá`
^tÝrRÕù#êwðãTÓK"Íû´Ëß!øòOf«

As a hex-string:

9F419458213FD6CD4CB9094A10D3B0FB
8F30E0616834DB7BB517CCE1600A5E74
DD7252D5F923EA77F0E354D34B9F22CD
FB80B4CBDF21F80E94F24F9A66AB9112

Explanation:

O‘ḅ256b¢*13%¢ḅ¢ḃ256’Ọ
O                     convert each into codepoint
 ‘ḅ256                convert from bijective base 256 to integer
      b¢              convert from integer to base N
        *13           map each to its 13th power
           %¢         modulo N
             ḅ¢       convert to integer from base N
               ḃ256’  convert from integer to bijective base 256
                    Ọ convert each from codepoint

Where N is encoded by the string:

“¥@ɦ⁺€€Ṅ`yȤDƁWĊ;Y^y⁻U ⁸ßɠƁXẹṡWZc'µ÷ḷỊ0ÇtṙA×Ḃß4©qV)iḷỊDƭ Mṛ+<ṛ_idðD’

which is the number

15465347049748408180402050551405372385300458901874153987195606642192077081674726470827949979631079014102900173229117045997489671500506945449681040725068819

Also, this is the RSA method with N given above and public key 13. Cracking this is equivalent to finding the two prime factors of N, which has 512 bits.

Leaky Nun

Posted 2017-07-19T18:12:43.117

Reputation: 45 011

2I love that your encrypted string looks like your code – Skidsdev – 2017-07-20T10:18:12.450

Using this wonderful program, I'm sure I can crack your solution a couple millennia after the heat death of the universe.

– Socratic Phoenix – 2017-07-20T13:52:52.217

@SocraticPhoenix factorization by trial division can never come close to quadratic sieve. – Leaky Nun – 2017-07-20T13:57:18.073

@LeakyNun I don't understand your big math words... – Socratic Phoenix – 2017-07-20T13:59:48.237

@SocraticPhoenix your program tries each factor from 2, while quadratic sieve is much faster. It can factorize a 256-bit semiprime in 6 minutes, whereas your program would have taken an eternity.

– Leaky Nun – 2017-07-20T14:34:06.940

Quadratic sieve is the best option for integers up to approx. 100 decimal digits. Beyond that, you should use the General Number Field Sieve. Factoring this 512-bit integer (supposed semiprime) in less than one week would probably have a dissuasive enough CPU cost for the context of this challenge, though. – Arnauld – 2017-07-20T16:02:06.220

@Arnauld How many bits are usually used then? – Leaky Nun – 2017-07-20T16:08:41.363

@LeakyNun I think the current recommended standard is 2048-bit keys. 512 is probably too much for a recreational challenge but definitely not enough for any sensitive data. – Arnauld – 2017-07-20T16:17:21.963

@Arnauld how quickly would you expect a quadratic sieve to factor this number? Aaand do you know of any Java implementations of the general number field sieve (all the math is over my head, but I know enough to call a library function!). – Socratic Phoenix – 2017-07-20T21:01:19.370

@SocraticPhoenix I may be wrong, but I don't think QS can factor this in any reasonable time. As for a Java implementation of GNFS, this one maybe?

– Arnauld – 2017-07-21T01:00:55.437

I've already danced this dance with @Sp3000, and 512 bit RSA costs around ~$70 to crack: https://codegolf.stackexchange.com/questions/107014/hidden-inversions-robbers-thread/107660#107660.

– orlp – 2017-07-21T03:28:36.387

@orlp in electrical costs? That seems like a kind of arbitrary number... – Socratic Phoenix – 2017-07-21T11:22:47.697

@SocraticPhoenix Sp3000 used c4.8xlarge spot instances on Amazon EC2. As of today, they cost $0.37 per hour for Linux (at least for their Ohio data center).

– Arnauld – 2017-07-21T16:29:43.490

@Arnauld interesting... it looks like my measly secondary computer won't be able to get this done in < 5 days anyway... gg Leaky Nun, gg – Socratic Phoenix – 2017-07-21T16:33:16.893

3

JavaScript (ES6), 43 + 33 = 76 bytes Cracked by Leaky Nun

Encryption function, 43 bytes:

s=>[...s].sort(_=>Math.cos(i++),i=0).join``

Encrypted message, 33 bytes:

NB: This encryption method is browser-dependent.

FireFox: "ty a)s kaasoeocr!hTt; o s  -cwaoo"
Chrome : "oht aasoaoas   e)tosr;oky c!-cw T"
Edge   : "tskso ;- caroteoTha wa soo ay c!)"

Arnauld

Posted 2017-07-19T18:12:43.117

Reputation: 111 334

T! a)o khas eotrto-c; o sa cwsaoy – Leaky Nun – 2017-07-19T18:41:34.593

@LeakyNun Err ... no. – Arnauld – 2017-07-19T18:42:31.293

What does my answer produce instead? – Leaky Nun – 2017-07-19T18:43:24.323

Which browser are you using? I'm using Chrome. – Leaky Nun – 2017-07-19T18:44:39.493

Wild guess, but is it !o a)w k asoeotryatc; s s oT-caoh? – Erik the Outgolfer – 2017-07-19T18:46:07.397

If you don't mind, can you provide the output for "0123456789abcdefghijklmnopqrstvuw"? – Leaky Nun – 2017-07-19T18:46:14.750

6That was soooo easy to crack! -;) (I used firefox to crack it) – Leaky Nun – 2017-07-19T18:46:32.653

3

Braingolf, Cracked

(d1&,&g)&@

Try it online!

Encrypted message, 45 bytes (UTF-8)

°Áݭїϳ{ًչםק{їϳэÁק{|э³קѡ|

Hexcodes of encrypted message

C2 B0 C3 81 DD AD D1 97 CF
B3 C2 90 7B D9 8B D5 B9 D7
9D D7 A7 7B D1 97 CF B3 D1
8D C3 81 D7 A7 7B 7C D1 8D
C2 B3 D7 A7 D1 A1 7C C2 85

Decrypted message

C'mon, this one's *easy*!

Explanation

(d1&,&g)&@  Implicit input from commandline args
(......)    Foreach loop, foreach codepoint of input
 d          Split into digits
  1         Push 1
   &,       Reverse
     &g     Concatenate
        &@  Print

Decoder

A decoder can be made by changing only 3 characters. Simply remove the 1, and insert $_ inbetween &, and &g

(d&,$_&g)&@

Skidsdev

Posted 2017-07-19T18:12:43.117

Reputation: 9 656

Can you provide a TIO? – user41805 – 2017-07-20T13:47:08.227

1C'mon, this one's *easy*! – KSmarts – 2017-07-20T14:59:29.960

@KSmarts Correct! – Skidsdev – 2017-07-20T15:05:14.727

g is undocumented? – Leaky Nun – 2017-07-20T15:42:27.883

Is this bijective? – Leaky Nun – 2017-07-20T15:44:06.547

@LeakyNun yes, each character in the output has a character value equal to the corresponding input's value reversed and prefixed with a 1.

For example a space (32) becomes 123 – Skidsdev – 2017-07-20T15:47:03.387

That doesn't mean it's bijective, that just means it's well-defined. – Leaky Nun – 2017-07-20T15:59:46.277

@LeakyNun my understanding of bijective is that it must have no collisions – Skidsdev – 2017-07-20T16:00:54.167

No, that just means injective; the comments clarified that the range must be all byte strings. – Leaky Nun – 2017-07-20T16:05:49.727

@LeakyNun I had a bit of trouble with this one because g does seem to be undocumented. At least, on the github readme and on Esolangs.org – KSmarts – 2017-07-20T19:33:32.867

3

JavaScript (ES6), 96+9=105 bytes

q=>Buffer(q).map((a,i,d)=>d[i-1]^Math.abs(1e16*Math.sin(d[i]+i))%255).sort((a,i)=>Math.tan(a*i))

Ciphertext (hex-encoded): 7d111c74b99faff76a

Try it online!

Sample outputs (using V8 engine):

abc123 -> db48ea4f86b9

Hello -> 1b3420f5ab

iovoid

Posted 2017-07-19T18:12:43.117

Reputation: 411

Invalid submission: multiple plaintext generate the same ciphertext. For example: "C", "D". This only counts for the first char. Of the 256 possible inputs, only 165 unique outputs. – Mark Jeronimus – 2018-09-20T11:10:17.587

It is bijective for the intended range (ASCII A to ASCII z) – iovoid – 2018-10-20T01:07:04.673

I just told you it's not. Just try your code with respectively "C" and "D" as the input string. Same output string 76. – Mark Jeronimus – 2018-10-22T07:46:23.913