Implementieren Sie ein One-Time-Pad

13

Hintergrund

Ein One-Time-Pad ist eine Form der Verschlüsselung, die sich bei sachgemäßer Verwendung als unmöglich zu knacken erwiesen hat.

Die Verschlüsselung wird durchgeführt, indem ein Klartext (der nur aus den Buchstaben AZ besteht) und eine zufällige Zeichenfolge mit der gleichen Länge (auch nur aus den Buchstaben) generiert wird. Diese Zeichenfolge fungiert als Schlüssel. Jedes Zeichen im Klartext wird dann mit dem entsprechenden Zeichen im Schlüssel gepaart. Der Chiffretext wird wie folgt berechnet: Für jedes Paar werden beide Zeichen in Zahlen umgewandelt (A = 0, B = 1, ... Z = 25). Die beiden Zahlen werden modulo 26 addiert. Diese Zahl wird wieder in ein Zeichen umgewandelt.

Entschlüsselung ist genau das Gegenteil. Die Zeichen im Chiffretext und im Schlüssel werden gepaart und in Zahlen umgewandelt. Der Schlüssel wird dann vom Chiffretextmodul 26 subtrahiert und das Ergebnis wird zurück in ein Zeichen AZ umgewandelt.

Die Herausforderung

Ihre Herausforderung besteht darin, das kürzestmögliche Programm zu schreiben, mit dem ein einmaliges Pad sowohl verschlüsselt als auch entschlüsselt werden kann.

In der ersten Eingabezeile (in STDIN) steht entweder das Wort "ENCRYPT" oder das Wort "DECRYPT".

Wenn das Wort verschlüsselt ist, ist die nächste Zeile der Klartext. Ihr Programm sollte zwei Zeilen ausgeben (an STDOUT), wobei die erste der Schlüssel und die zweite der Chiffretext ist.

Wenn das Wort entschlüsselt ist, erhält Ihr Programm zwei weitere Eingabezeilen. Die erste Zeile ist der Schlüssel, und die zweite Zeile ist der Chiffretext. Ihr Programm sollte eine Zeile ausgeben, bei der es sich um den entschlüsselten Klartext handelt.

Klartext, Chiffretext und Schlüssel sollten immer aus Großbuchstaben AZ bestehen. Sie bestehen immer aus einer einzelnen Zeile und enthalten keine Leerzeichen.

Der Schlüssel sollte immer zufällig sein. Es sollten keine großen Teile zwischen den Läufen wiederholt werden, und es sollten keine Muster im Text vorhanden sein.

Zwei einfache Beispiele:

ENCRYPT
HAPPYBIRTHDAY
>ABKJAQLRJESMG
>HBZYYRTICLVME

DECRYPT
ABKJAQLRJESMG
HBZYYRTICLVME
>HAPPYBIRTHDAY

Das >stellt dar, welche Zeilen ausgegeben werden, sodass Sie dieses Symbol nicht als Ausgabe drucken müssen.

PhiNotPi
quelle
7
Nicht zu kritisieren , die Herausforderung auf seine eigenen Verdienste (was in Ordnung sind), aber ich bin gehen die Kryptographie hier zu kritisieren. Was Sie beschreiben, ist eine "Stream-Verschlüsselung", da sie von einem PRNG abhängt (es sei denn, Ihr Computer hat Zugriff auf eine Quelle oder echte Zufälligkeit (und wenn die Linux-Implementierung von / dev / urandom eine Frage der Debatte ist) Wenn der Schlüssel zum Zeitpunkt der Verschlüsselung entwickelt wird, ist dies die einzige wirklich gute Verwendung für ein OTP, bei dem die sichere Kommunikation zeitversetzt erfolgt.
dmckee --- Ex-Moderator Kätzchen
1
Außerdem sind alle Herausforderungen standardmäßig sprachunabhängig, daher habe ich dieses Tag entfernt.
dmckee --- Ex-Moderator Kätzchen
7
@dmckee In Bezug auf Ihren ersten Kommentar stimme ich zu, weshalb ich nicht beabsichtige, diese Antworten zur Sicherung meiner Kommunikation zu verwenden.
PhiNotPi
1
Das hätte meiner Meinung nach mehr Spaß gemacht, als das Problem durch Zufälligkeit zu lösen. Wenn Sie eine Zufallsquelle ( /dev/random, haveged) angegeben haben, verschlüsseln Sie diese, indem Sie die Ords mit den Bytes versehen und entschlüsseln Sie sie, indem Sie sie mit dem Schlüssel versehen. gist.github.com/5078264 der schlüssel oder die zufälligkeit kann aus stdin gelesen werden, die nachricht oder der verschlüsselte text kann ein dateinamenargument sein.
ixtmixilix
@PhiNotPi Ich habe einen Vorschlag. Warum nicht einen Bonus geben, wenn sie eine wirklich zufällige Quelle verwenden (wie /dev/hwrnganstelle von Pseudo-Zufall (was es technisch kaputt macht.)
PyRulez

Antworten:

8

GolfScript, 53 Zeichen

n%(0=2%{~.,[{26rand 65+}*]:K]}*zip{{-}*~)26%65+}%K]n*

Dies ist eine Aufgabe, für die GolfScript nahezu perfekt geeignet zu sein scheint.

Um den Code kurz zu halten, verwende ich denselben Code sowohl für die Verschlüsselung als auch für die Entschlüsselung: Zum Entschlüsseln subtrahiere ich den Schlüssel vom Chiffretext, während ich zum Verschlüsseln zuerst einen zufälligen Chiffretext generiere und dann den Klartext davon subtrahiere. Trotzdem nimmt der zusätzliche Code für die Implementierung des Verschlüsselungsmodus etwas mehr als die Hälfte der Programmlänge in Anspruch.

De-Golf-Version mit Kommentaren:

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
Ilmari Karonen
quelle
4

Rubin ( 200 185)

Probeläufe + 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,:-]])
jsvnm
quelle
s[k=(p=f).map{rand 26}],r[k,p,:-]sollte geschrieben werdens[k=f.map{rand 26}],r[k,$_,:-]
Hauleth
@Hauleth nein das geht nicht, da $_nur die letzte Zeile durchgelesen wird gets. fauch .scan(/./).map{|b|b.ord-65}nach dem Lesen einer Zeile.
Jsvnm
3

Haskell, 203 Zeichen

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=toEnum$65+o x%o k`mod`26
o c=fromEnum c-65;z=zipWith

Beispiel:

$ runghc OneTimePad.hs <<< $'ENCRYPT\nHELLOWORLD'
QMNQKGFZFD
XQYBYCTQQG
$ runghc OneTimePad.hs <<< $'DECRYPT\nQMNQKGFZFD\nXQYBYCTQQG'
HELLOWORLD
Hammar
quelle
3

Perl, 220 171 Zeichen

if(<>=~/D/){$_=<>;$w=<>;print chr((ord(substr$w,$i++,1)-ord$1)%26+65)while/(.)/g}else{$_=<>;$c.=chr((ord($1)-65+($i=rand(26)))%26+65),print chr$i+65while/(.)/g;print$/.$c}

Probelauf:

ENCRYPT
HELLO
CCTKK
JGEVY

DECRYPT
CCTKK
JGEVY
HELLO

Hinweis: Zumindest wenn ich es ausführe, wird "Drücken Sie eine beliebige Taste, um fortzufahren ..." an das Ende der letzten Ausgabe angehängt. Ich hoffe das ist ok, da es nicht Teil des Programms ist. Wenn nicht, kann ich es so machen, dass es in der nächsten Zeile erscheint.

Dies ist mein erstes richtiges Programm in Perl und mein erstes Golfprogramm überhaupt, daher würde ich mich über Tipps sehr freuen. Auch habe ich gefunden/(.)/g im Internet gefunden, aber ich habe keine Ahnung, wie es funktioniert (ist es ein regulärer Ausdruck? Ich habe die noch nicht gelernt). Kann es mir jemand erklären?

EDIT: Dank an Ilmari Karonen, die mir bei den Regexps geholfen hat, habe ich mein neues Wissen genutzt, um 7 Zeichen zu speichern!

Erweiterte, leicht lesbare Version:

if(<>=~/D/){
    $_=<>;
    $w=<>;
    print chr((ord(substr$w,$i++,1)-ord$1)%26+65)while/(.)/g
}
else{
    $_=<>;
    $c.=chr((ord($1)-65+($i=rand(26)))%26+65),print chr$i+65while/(.)/g;
    print$/.$c
}
Kommando
quelle
Ja, /(.)/gist ein regulärer Ausdruck. Sie werden definitiv diese lernen wollen, wenn Sie Perl Golf spielen wollen. perldoc.perl.org/perlre.html ist kein schlechter Startplatz.
Ilmari Karonen
2

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)

Ich glaube, dass dies genau den Spezifikationen entspricht (einschließlich der '>'am Anfang der Eingabe stehenden Eingabeaufforderungen). Die Eingabe wird nicht validiert, daher denke ich, dass nur eine Müllausgabe erzeugt wird, wenn Sie Zeichen außerhalb von eingeben [A-Z]. Es wird auch nur der erste Buchstabe des Eingabebefehls überprüft. Alles, was mit beginnt, Dführt zu einer Entschlüsselung, und alles andere führt zu einer Verschlüsselung.

Gordon Bailey
quelle
Ich habe nicht damit gerechnet, dass Sie das drucken >, ich habe es nur verwendet, um zu demonstrieren, welche Zeilen ausgegeben wurden. Sie müssen diese nicht implementieren.
PhiNotPi
Ok, cool, dann 9 Zeichen weniger.
Gordon Bailey
1

C ++ - 220 241 Zeichen, 4 Zeilen

#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);}

Bearbeiten 1- Die MSVS-Standardbibliothek scheint eine Menge unnötiger Dateien zu enthalten, was bedeutete, dass ios über alle benötigten Includes verfügte, dies funktionierte jedoch nicht mit anderen Compilern. Das ios wurde für die tatsächlichen Dateien geändert, die die benötigten Funktionen in cstdlib und cstdio enthalten. Vielen Dank an Ilmari Karonen für den Hinweis.

Scott Logan
quelle
Kompiliert nicht für mich: g++ otp.cppsagtotp.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
Ilmari Karonen
Huh, das ist komisch, ich benutze Visual Studio. <Ios> muss vom Standard abweichen, damit <conio.h> und <stdio.h> in den Includes enthalten sind. Ich ging davon aus, dass die Header bei verschiedenen Implementierungen immer die gleichen Dateien enthielten. Ich werde es später untersuchen, danke.
Scott Logan
1

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

Beispielausgabe:

$ python onetimepad.py 
ENCRYPT
HELLOWORLD
UXCYNPXNNV
BBNJBLLEYY
$ python onetimepad.py 
DECRYPT
UXCYNPXNNV
BBNJBLLEYY
HELLOWORLD

Zeichenanzahl:

$ wc -c onetimepad.py 
270 onetimepad.py
tomcant
quelle
1

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
)

Alle notwendigen Leerzeichen gezählt.

Kommentierte 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)
)
jpjacobs
quelle
1

C # ( 445 416)

Aggregat vergessen. Schneiden Sie ein gutes Stück ab.

Etwas golfen:

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);
        }
    }
}

}

Golf gespielt:

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);}}}}
Farami
quelle
0

C (159 + 11 für Compiler-Flags)

Golf gespielt:

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);
}

Kompilieren mit -Dg=gets(s).

Beispiel:

$./onetimepad
ENCRYPT
FOOBAR
>PHQGHU
>UVEHHL
$./onetimepad
DECRYPT
PHQGHU
UVEHHL
>FOOBAR
es1024
quelle
Ich erhalte jedes Mal den gleichen Schlüssel, wenn ich ihn ausführe - es gibt keine Zufälligkeit.
Feersum
0

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}

Verwendung:

var str = "HELLOWORLD";
var key = R(str.length);
var enc = X(str, key, false);
console.log(enc);
console.log(X(enc,key, true));
Wolfhammer
quelle
0

Ruby - 184 179 177 Zeichen

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}*''

Führen Sie es so aus: $ ruby pad-lock.rb

Hier ist die ungolfed version falls jemand interessiert ist

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("")
addison
quelle