Background
A one-time pad is a form of encryption that has been proven impossible to crack if used properly.
Encryption is performed by taking a plaintext (comprised of only letters A-Z) and generating a random string on the same length (also only letters). This string acts as the key. Each character in the plaintext is then paired up with the corresponding character in the key. The ciphertext is computed as follows: For each pair, both characters are converted to numbers (A=0, B=1, ... Z=25). The two numbers are added modulo 26. This number is the converted back into a character.
Decryption is exactly the opposite. The characters in the ciphertext and key are paired up and converted to numbers. The key is then subtracted from the ciphertext modulo 26, and the result is converted back into a character A-Z.
The Challenge
Your challenge is to write the shortest program possible that can both encrypt and decrypt a one-time pad.
On the first line of input (to STDIN), there will be either the word "ENCRYPT" or the word "DECRYPT".
If the word is encrypt, then the next line will be the plaintext. Your program should output two lines (to STDOUT), the first being the key, and the second being the ciphertext.
If the word is decrypt, your program will get two more line of input. The first line will be the key, and the second line will be the ciphertext. You program should output one line, which will be the plaintext that has been decrypted.
The plaintext, ciphertext, and key should always consist of uppercase letters A-Z. They will always be a single line and contain no whitespace.
The key should always be random. No large parts of it should repeat between runs, and there should be no patterns that can be found in the text.
Two simple examples:
ENCRYPT
HAPPYBIRTHDAY
>ABKJAQLRJESMG
>HBZYYRTICLVME
DECRYPT
ABKJAQLRJESMG
HBZYYRTICLVME
>HAPPYBIRTHDAY
The > represents which lines are output, so you don't have to print that symbol as output.
13 Answers 13
GolfScript, 53 chars
n%(0=2%{~.,[{26rand 65+}*]:K]}*zip{{-}*~)26%65+}%K]n*
This is a task for which GolfScript seems just about perfectly suited.
To keep the code short, I'm using the same code for both encryption and decryption: to decrypt, I subtract the key from the ciphertext, while for encryption, I first generate a random ciphertext and then subtract the plaintext from it. Even so, the extra code for implementing encryption mode takes just a little over half the length of the program.
De-golfed version with comments:
n % # split input into an array of lines
# KEY GENERATION FOR ENCRYPTION MODE:
( # extract the first line from the array
0 = 2 % # check if the first char of that line is odd (E = 69)...
{ # ...and execute this block if it is:
~ # dump the remaining lines (of which the should be only one) on the stack
. , # calculate the length of the last line...
[ { 26 rand 65 + } * ] # ...make an array of that many random letters...
:K # ...and assign it to K
] # collect all the lines, including K, back into an array
} *
# ENCRYPTION / DECRYPTION ROUTINE:
zip # transpose the array of 2 n-char strings into n 2-char strings...
{ # ...and execute this block for each 2-char string:
{-} * # subtract the second char code from the first
~ ) # negate the result (using the two's complement trick -x = ~x+1)
26 % 65 + # reduce modulo 26 and add 65 = A
} %
# OUTPUT:
K ] n* # join the result and K (if defined) with a newline, stringifying them
Ruby ((削除) 200 (削除ここまで) 185)
sample runs + wc:
$ ruby onetimepad.rb
ENCODE
ANOTHERTESTINPUTZZZ
ZYCLGHDWLDASFUTHWKC
BPMIBXOXTPTQIVBMDPX
$ ruby onetimepad.rb
DECODE
ZYCLGHDWLDASFUTHWKC
BPMIBXOXTPTQIVBMDPX
ANOTHERTESTINPUTZZZ
$ wc onetimepad.rb
4 7 185 onetimepad.rb
def f;gets.scan(/./).map{|b|b.ord-65};end
s=->a{a.map{|b|(b+65).chr}*''}
r=->b,a,o{s[a.zip(b).map{|a,b|(a.send o,b)%26}]}
puts(gets=~/^D/?r[f,f,:+]:[s[k=(p=f).map{rand 26}],r[k,p,:-]])
-
\$\begingroup\$
s[k=(p=f).map{rand 26}],r[k,p,:-]should be writtens[k=f.map{rand 26}],r[k,$_,:-]\$\endgroup\$Hauleth– Hauleth2012年03月19日 21:25:24 +00:00Commented Mar 19, 2012 at 21:25 -
\$\begingroup\$ @Hauleth no that doesn't work, as
$_is just the last line read bygets.falso does.scan(/./).map{|b|b.ord-65}after reading a line. \$\endgroup\$jsvnm– jsvnm2012年03月19日 21:50:36 +00:00Commented Mar 19, 2012 at 21:50
APL (Dyalog Unicode), 46 bytes
⎕A[26|{'N'∊⍞:⍉x,⍪(⎕A⍳w)+x←26?⍨⍴w←⍞⋄-⌿⎕A⍳↑⍞⍞}1]
The current full program is the result of a 2hr long session at The APL Orchard., with a lot of golfing input from Adám (-13 bytes!).
Requires ⎕IO←0 (0-indexing).
Explanation
⎕A[26|{'N'∊⍞:⍉x,⍪(⎕A⍳w)+x←26?⍨⍴w←⍞⋄-⌿⎕A⍳↑⍞⍞}1]
{ }1 inner fn(called with junk param)
⍞ first input
'N'∊ is 'N' present in it?
:⍉x,⍪(⎕A⍳w)+x←26?⍨⍴w←⍞ if so, eNcrypt:
w←⍞ store message in w
26?⍨⍴ generate 26 random numbers,
x← store in x
(⎕A⍳w)+ add that to the indices in the alphabet
⍪ table them
x, join with the random numbers
⍉ transpose to get key and encrypted value
⋄-⌿⎕A⍳↑⍞⍞ else, decrypt:
⍞⍞ input key and value
↑ convert to matrix
⎕A⍳ get the indices of both in the alphabet
-⌿ difference of all columns
26| mod the result of the inner fn.
[ ] index the result of the program in
⎕A the capitalized alphabet.
Haskell, 203 characters
import Random
main=newStdGen>>=interact.(unlines.).(.lines).f.randomRs('A','Z')
f k['E':_,x]=[z const k x,z(e(+))k x]
f _[_,k,x]=[z(e(-))k x]
e(%)k x=toEnum65ドル+o x%o k`mod`26
o c=fromEnum c-65;z=zipWith
Example:
$ runghc OneTimePad.hs <<< $'ENCRYPT\nHELLOWORLD'
QMNQKGFZFD
XQYBYCTQQG
$ runghc OneTimePad.hs <<< $'DECRYPT\nQMNQKGFZFD\nXQYBYCTQQG'
HELLOWORLD
Perl, (削除) 220 (削除ここまで) 171 characters
if(<>=~/D/){$_=<>;$w=<>;print chr((ord(substr$w,$i++,1)-ord1ドル)%26+65)while/(.)/g}else{$_=<>;$c.=chr((ord(1ドル)-65+($i=rand(26)))%26+65),print chr$i+65while/(.)/g;print$/.$c}
Sample Run:
ENCRYPT
HELLO
CCTKK
JGEVY
DECRYPT
CCTKK
JGEVY
HELLO
Note: at least when I run it, "Press any key to continue..." is appended to the end of the last output. I hope this is ok, because it isn't part of the program. If not, I can make it so it appears on the next line.
This is my first real program in Perl, and my first golf ever, so I would really appreciate tips. Also, I found /(.)/g on the internet, but I have no idea how it works (is it a regular expression? I haven't learnt those yet). Can somebody explain it to me?
EDIT: Thanks to Ilmari Karonen for helping me out with the regexps, I used my new knowledge to save 7 characters!
Expanded, slightly legible version:
if(<>=~/D/){
$_=<>;
$w=<>;
print chr((ord(substr$w,$i++,1)-ord1ドル)%26+65)while/(.)/g
}
else{
$_=<>;
$c.=chr((ord(1ドル)-65+($i=rand(26)))%26+65),print chr$i+65while/(.)/g;
print$/.$c
}
-
\$\begingroup\$ Yes,
/(.)/gis a regexp. You'll definitely want to learn those if you're going to play Perl golf. perldoc.perl.org/perlre.html is not a bad starting place. \$\endgroup\$Ilmari Karonen– Ilmari Karonen2012年03月17日 18:21:39 +00:00Commented Mar 17, 2012 at 18:21
Python - (削除) 304 (削除ここまで) 295
import random
r=raw_input
R=lambda s:range(len(s))
o=lambda c:ord(c)-65
j=''.join
if r()[0]=='D':
s=r()
d=r()
print j(chr((o(s[i])-o(d[i]))%26+65)for i in R(s))
else:
s=r()
d=[random.randint(0,26)for i in R(s)]
print j(chr((o(s[i])+d[i])%26+65)for i in R(s))
print j(chr(n+65)for n in d)
I believe that this meets the specs exactly (削除) (Including the It does not validate input, so I think that it will just produce garbage output if you give it characters outside of '>' at the start of the input prompts.) (削除ここまで)[A-Z]. It also only checks the first letter of the input command. Anything starting with D will result in a decryption and anything else at all will result in an encryption.
-
\$\begingroup\$ I didn't expect you to print the
>, I was just using it to demonstrate which lines were output. You don't have to implement those. \$\endgroup\$PhiNotPi– PhiNotPi2012年03月16日 22:32:10 +00:00Commented Mar 16, 2012 at 22:32 -
\$\begingroup\$ Ok, cool, 9 fewer characters then. \$\endgroup\$Gordon Bailey– Gordon Bailey2012年03月16日 22:37:10 +00:00Commented Mar 16, 2012 at 22:37
C++ - (削除) 220 (削除ここまで) 241 chars, 4 lines
#include<cstdlib>
#include<cstdio>
#define a scanf("%s"
char i,s[99],t[99];int main(){a,t);a,s);if(t[0]>68){for(;s[i];++i)s[i]=(s[i]+(t[i]=rand()%26+65))%26+65;puts(t);}else for(a,t);s[i];++i){s[i]=65+t[i]-s[i];if(s[i]<65)s[i]+=26;}puts(s);}
Edit 1- The MSVS standard library seems to include a lot of unnecessary files which meant that ios had all the includes that I needed but this didn't work with other compilers. Changed ios for the actual files that the functions needed appear in cstdlib and cstdio. Thanks to Ilmari Karonen for pointing this out.
-
\$\begingroup\$ Doesn't compile for me:
g++ otp.cppsaysotp.cpp: In function ‘int main()’: otp.cpp:3: error: ‘scanf’ was not declared in this scope otp.cpp:3: error: ‘rand’ was not declared in this scope otp.cpp:3: error: ‘puts’ was not declared in this scope otp.cpp:3: error: ‘puts’ was not declared in this scope\$\endgroup\$Ilmari Karonen– Ilmari Karonen2012年03月17日 14:39:55 +00:00Commented Mar 17, 2012 at 14:39 -
\$\begingroup\$ Huh, that's strange, I use visual studio. It must be non-standard for <ios> to have <conio.h> and <stdio.h> in it's includes. I assumed the headers always included the same files on different implementations. I'll look into it later, Thanks. \$\endgroup\$Scott Logan– Scott Logan2012年03月17日 15:25:05 +00:00Commented Mar 17, 2012 at 15:25
Python - 270
import random
i=raw_input
m=i()
a=i()
r=range(len(a))
o=ord
j=''.join
if m=='ENCRYPT':
k=j(chr(65+random.randint(0,25)) for x in r)
R=k+"\n"+j(chr((o(a[x])+o(k[x]))%26+65) for x in r)
elif m=='DECRYPT':
k=i()
R=j(chr((o(k[x])-o(a[x]))%26+65) for x in r)
print R
Sample output:
$ python onetimepad.py
ENCRYPT
HELLOWORLD
UXCYNPXNNV
BBNJBLLEYY
$ python onetimepad.py
DECRYPT
UXCYNPXNNV
BBNJBLLEYY
HELLOWORLD
Character count:
$ wc -c onetimepad.py
270 onetimepad.py
J : 94 bytes
3 :0]1
c=:(26&|@)(&.(65-~a.&i.))
r=:1!:1@1:
((],:+c)[:u:65+[:?26$~#)@r`(r-c r)@.('D'={.)r 1
)
All necessary white space counted.
Commented version:
3 :0]1 NB. Make a function and call it
c=:(26&|@)(&.(65-~a.&i.)) NB. Adverb for operating on the alphabet
NB. (used for adding and subtracting the pad)
r=:1!:1@1: NB. Read input line and decide (right to left)
((],:+c)[:u:65+[:?26$~#)@r ` (r-c r) @. ('D'={.)r 1
NB. Encryption (ger 0) | Decryption (ger 1)| Agenda
NB. pad,:(crypt=:plain + pad)| crypt - pad | If D is first input, do (ger 1), else do (ger 0)
)
C# ((削除) 445 (削除ここまで) 416)
Forgot about Aggregate. Cut off a good bit.
Somewhat golfed:
namespace G {
using System;
using System.Linq;
using x = System.Console;
class P {
static void Main() {
string p = "", c = "", k = "";
Random r = new Random();
int i = 0;
if (x.ReadLine()[0] == 'E') {
p = x.ReadLine();
k=p.Aggregate(k,(l,_)=>l+(char)r.Next(65,90));
c=p.Aggregate(c,(m,l)=>m+(char)((l+k[i++])%26+65));
x.WriteLine(k + "\n" + c);
} else {
k = x.ReadLine();
c = x.ReadLine();
p=c.Aggregate(p,(l,a)=>l+(char)((a-k[i++]+26)%26+65));
x.WriteLine(p);
}
}
}
}
Golfed:
namespace G{using System;using System.Linq;using x=System.Console;class P{static void Main(){string p="",c="",k="";Random r=new Random();int i=0;if (x.ReadLine()[0]=='E'){p=x.ReadLine();k=p.Aggregate(k,(l,_)=>l+(char)r.Next(65,90));c=p.Aggregate(c,(m,l)=>m+(char)((l+k[i++])%26+65));x.WriteLine(k+"\n"+c);}else{k=x.ReadLine();c=x.ReadLine();p=c.Aggregate(p,(l,a)=>l+(char)((a-k[i++]+26)%26+65));x.WriteLine(p);}}}}
JavaScript 239
var F=String.fromCharCode
function R(l){var k='';while(l--)k+=F(~~(Math.random()*26)+65);return k}
function X(s,k,d){var o='',i=0,a,b,c
while(i<s.length)a=s.charCodeAt(i)-65,b=k.charCodeAt(i++)-65,c=d?26+(a-b):a+b,o+=F((c%26)+65)
return o}
Usage:
var str = "HELLOWORLD";
var key = R(str.length);
var enc = X(str, key, false);
console.log(enc);
console.log(X(enc,key, true));
C (159 + 11 for compiler flags)
Golfed:
d(a,b){return(a+b+26)%26+65;}a;char s[999],b,*c=s-1;main(){g;a=*s-69;g;while(*++c)a?b=-*c,*c=getchar():putchar(b=rand()%26+65),*c=d(*c,b);a||puts("");puts(s);}
Ungolfed:
d(a,b){
//*a = (*a + b - 2*65 + 26) % 26 + 65;
return (a + b + 26) % 26 + 65;
}
a; char s[999], b, *c = s-1;
main(){
gets(s);
a = *s - 69; // -1 if decrypt 0 if encrypt
gets(s);
while(*++c){
if(!a)
putchar(b = rand() % 26 + 65); // 'A'
else
b = -*c, *c = getchar();
*c = d(*c,b);
}
if(!a) puts("");
puts(s);
}
Compile with -Dg=gets(s).
Example:
$./onetimepad
ENCRYPT
FOOBAR
>PHQGHU
>UVEHHL
$./onetimepad
DECRYPT
PHQGHU
UVEHHL
>FOOBAR
-
\$\begingroup\$ I get the same key every time I run it--there is no randomness. \$\endgroup\$feersum– feersum2014年08月20日 01:39:48 +00:00Commented Aug 20, 2014 at 1:39
Ruby - (削除) 184 (削除ここまで) (削除) 179 (削除ここまで) 177 chars
def g;gets.scan(/./).map{|c|c.ord-65}end
m,=g
k=(s=g).map{rand 26}
m==4?(puts k.map{|c|(c+65).chr}*'';y=:+):(k,s=s,g)
puts s.zip(k).map{|c,o|(c.send(y||:-,o).to_i%26+65).chr}*''
Run it like this: $ ruby pad-lock.rb
Here is the ungolfed version if anyone is interested (it's not quite up to date with the golfed one though)
def prompt
gets.scan(/./).map{ |c|c.ord - 65 }
end
mode = prompt[0]
operator = :-
secret = prompt
key = secret.map { |char| rand(26) }
if mode == 4 # the letter E, or ENCRYPT
key.map { |char| print (char + 65).chr }
puts
operator = :+
else
# make the old secret the new key,
# and get a new secret (that has been encrypted)
key, secret = secret, prompt
end
chars = secret.zip(key).map do |secret_char, key_char|
# if mode == 4 (E) then add, otherwise subtract
i = secret_char.send(operator, key_char).to_i
((i % 26) + 65).chr
end
puts chars.join("")
/dev/random,haveged), encrypt by xoring the ords with the bytes and decrypt by xoring them with the key. gist.github.com/5078264 the key or the randomness can be read from stdin, the message or cyphertext can be a filename argument. \$\endgroup\$/dev/hwrng, instead of using pseudo random (which technically makes it broken.) \$\endgroup\$