Zaimplementuj jednorazową podkładkę

13

tło

Szyfr z kluczem jednorazowym jest formą szyfrowania, który okazał niemożliwe do zgryzienia, jeśli są prawidłowo stosowane.

Szyfrowanie odbywa się poprzez pobranie zwykłego tekstu (składającego się tylko z liter AZ) i wygenerowanie losowego ciągu o tej samej długości (również tylko liter). Ten ciąg działa jak klucz. Każdy znak w tekście jawnym jest następnie sparowany z odpowiednim znakiem w klawiszu. Tekst zaszyfrowany jest obliczany w następujący sposób: Dla każdej pary oba znaki są konwertowane na liczby (A = 0, B = 1, ... Z = 25). Dwie liczby są dodawane modulo 26. Liczba ta jest konwertowana z powrotem na znak.

Deszyfrowanie jest dokładnie odwrotne. Znaki w tekście zaszyfrowanym i kluczu są sparowane i zamienione na liczby. Klucz jest następnie odejmowany od modulo 26 zaszyfrowanego tekstu, a wynik jest konwertowany z powrotem na znak AZ.

Wyzwanie

Twoim wyzwaniem jest napisanie możliwie najkrótszego programu, który może zarówno szyfrować, jak i deszyfrować jednorazowy pad.

W pierwszym wierszu wprowadzania (do STDIN) będzie słowo „ENCRYPT” lub słowo „DECRYPT”.

Jeśli słowo jest szyfrowane, następnym wierszem będzie zwykły tekst. Twój program powinien wypisać dwa wiersze (do STDOUT), pierwszy to klucz, a drugi to zaszyfrowany tekst.

Jeśli słowo jest deszyfrowane, twój program otrzyma jeszcze dwa wiersze wprowadzania. Pierwsza linia będzie kluczem, a druga linia będzie zaszyfrowanym tekstem. Twój program powinien wypisać jeden wiersz, który będzie odszyfrowanym tekstem jawnym.

Tekst jawny, tekst zaszyfrowany i klucz powinny zawsze składać się z wielkich liter AZ. Zawsze będą pojedynczą linią i nie będą zawierały białych znaków.

Klucz powinien zawsze być losowy. Żadne duże części nie powinny się powtarzać między seriami i nie powinno być żadnych wzorów, które można by znaleźć w tekście.

Dwa proste przykłady:

ENCRYPT
HAPPYBIRTHDAY
>ABKJAQLRJESMG
>HBZYYRTICLVME

DECRYPT
ABKJAQLRJESMG
HBZYYRTICLVME
>HAPPYBIRTHDAY

>Reprezentuje które linie są wyprowadzane, więc nie trzeba drukować ten symbol jako wyjścia.

PhiNotPi
źródło
7
Nie krytykować wyzwanie na jego własnych zasług (które są w porządku), ale ja mam zamiar krytykować kryptografii tutaj. To, co opisujesz, to „szyfr strumieniowy”, ponieważ zależy od PRNG (chyba że twój komputer ma dostęp do źródła lub prawdziwej losowości (i jeśli implementacja linuksowa / dev / urandom się liczy, to kwestia jakiejś debaty)), oraz klucz opracowany w czasie szyfrowania pokonuje jedyne naprawdę dobre zastosowanie OTP, jakim jest przesunięcie w czasie bezpiecznej komunikacji.
dmckee --- były moderator kociąt
1
Ponadto wszystkie wyzwania są domyślnie niezależne od języka, więc usunąłem ten tag.
dmckee --- były moderator kociąt
7
@dmckee Jeśli chodzi o twój pierwszy komentarz, zgadzam się, dlatego nie zamierzam używać tych odpowiedzi do zabezpieczenia mojej komunikacji.
PhiNotPi
1
IMO byłoby bardziej zabawne, gdyby pomijać przypadkowość; biorąc pod uwagę źródło losowości ( /dev/random, haveged), szyfruj przez xoring porządków bajtami i odszyfruj xoring kluczami. gist.github.com/5078264 klucz lub losowość można odczytać ze standardowego wejścia, wiadomość lub tekst alternatywny mogą być argumentem nazwy pliku.
ixtmixilix
@PhiNotPi Mam sugestię. Dlaczego nie dać premii, jeśli używają prawdziwie losowego źródła (na przykład /dev/hwrngzamiast pseudolosowego (co technicznie czyni go zepsutym).
PyRulez

Odpowiedzi:

8

GolfScript, 53 znaki

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

Jest to zadanie, do którego GolfScript wydaje się być idealnie dopasowany.

Aby kod był krótki, używam tego samego kodu zarówno do szyfrowania, jak i deszyfrowania: w celu odszyfrowania odejmuję klucz od tekstu zaszyfrowanego, podczas gdy w przypadku szyfrowania najpierw generuję losowy tekst zaszyfrowany, a następnie odejmuję od niego tekst jawny. Mimo to dodatkowy kod do implementacji trybu szyfrowania zajmuje nieco ponad połowę długości programu.

Wersja bez golfa z komentarzami:

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
źródło
4

Rubin ( 200 185)

przykładowe przebiegi + 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
źródło
s[k=(p=f).map{rand 26}],r[k,p,:-]należy napisaćs[k=f.map{rand 26}],r[k,$_,:-]
Hauleth
@Hauleth nie to nie działa, ponieważ $_jest to tylko ostatni wiersz czytany przez gets. frobi to również .scan(/./).map{|b|b.ord-65}po przeczytaniu linii.
jsvnm
3

Haskell, 203 znaków

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

Przykład:

$ runghc OneTimePad.hs <<< $'ENCRYPT\nHELLOWORLD'
QMNQKGFZFD
XQYBYCTQQG
$ runghc OneTimePad.hs <<< $'DECRYPT\nQMNQKGFZFD\nXQYBYCTQQG'
HELLOWORLD
hammar
źródło
3

Perl, 220 171 znaków

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}

Przykładowy przebieg:

ENCRYPT
HELLO
CCTKK
JGEVY

DECRYPT
CCTKK
JGEVY
HELLO

Uwaga: przynajmniej kiedy go uruchomię, na końcu ostatniego wyjścia dołącza się „Naciśnij dowolny klawisz, aby kontynuować ...”. Mam nadzieję, że jest to w porządku, ponieważ nie jest częścią programu. Jeśli nie, mogę to zrobić, aby pojawiło się w następnym wierszu.

To mój pierwszy prawdziwy program w Perlu i mój pierwszy golf w historii, więc naprawdę doceniłbym wskazówki. Znalazłem też /(.)/gw Internecie, ale nie mam pojęcia, jak to działa (czy to wyrażenie regularne? Jeszcze ich nie nauczyłem). Czy ktoś może mi to wytłumaczyć?

EDYCJA: Dzięki Ilmari Karonen za pomoc przy regexpsie wykorzystałem moją nową wiedzę, aby uratować 7 postaci!

Rozszerzona, mało czytelna wersja:

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
}
komandos
źródło
Tak, /(.)/gto wyrażenie regularne. Na pewno będziesz chciał się ich nauczyć, jeśli zamierzasz grać w golfa Perl. perldoc.perl.org/perlre.html nie jest złym miejscem początkowym.
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)

Uważam, że to dokładnie spełnia specyfikację (w tym '>'na początku monitów o wprowadzenie). Nie sprawdza poprawności danych wejściowych, więc myślę, że po prostu wyrzuci śmieci, jeśli podasz je poza znakami [A-Z]. Sprawdza także tylko pierwszą literę polecenia wejściowego. Wszystko, co zaczyna się od, Dspowoduje odszyfrowanie, a wszystko inne spowoduje szyfrowanie.

Gordon Bailey
źródło
Nie spodziewałem się, że wydrukujesz >, użyłem go tylko do zademonstrowania, które wiersze zostały wydrukowane. Nie musisz ich wdrażać.
PhiNotPi
Okej, spoko, wtedy 9 znaków mniej.
Gordon Bailey
1

C ++ - 220 241 znaków, 4 linie

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

Edycja 1- Standardowa biblioteka MSVS wydaje się zawierać wiele niepotrzebnych plików, co oznaczało, że ios miał wszystkie potrzebne pliki, ale nie działało to z innymi kompilatorami. Zmieniono iOS dla rzeczywistych plików, które potrzebne funkcje pojawiają się w cstdlib i cstdio. Dzięki Ilmari Karonen za zwrócenie na to uwagi.

Scott Logan
źródło
Nie kompiluje się dla mnie: g++ otp.cppmówiotp.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
To dziwne, używam studia wizualnego. <ios> musi zawierać <conio.h> i <stdio.h> w tym dołączeniu. Zakładałem, że nagłówki zawsze zawierały te same pliki w różnych implementacjach. Zajmę się tym później, dzięki.
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

Przykładowe dane wyjściowe:

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

Liczba znaków:

$ wc -c onetimepad.py 
270 onetimepad.py
jęczący
źródło
1

J: 94 bajty

3 :0]1
c=:(26&|@)(&.(65-~a.&i.))
r=:1!:1@1:
((],:+c)[:u:65+[:?26$~#)@r`(r-c r)@.('D'={.)r 1
)

Wszystkie niezbędne białe pola zostały policzone.

Skomentowana wersja:

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
źródło
1

C # ( 445 416)

Zapomniałem o agregacie. Odetnij trochę.

Nieco golfa:

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

}

Gra w golfa:

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
źródło
0

C (159 + 11 dla flag kompilatora)

Gra w golfa:

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

Nie golfowany:

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

Kompiluj z -Dg=gets(s).

Przykład:

$./onetimepad
ENCRYPT
FOOBAR
>PHQGHU
>UVEHHL
$./onetimepad
DECRYPT
PHQGHU
UVEHHL
>FOOBAR
es1024
źródło
Otrzymuję ten sam klucz za każdym razem, gdy go uruchamiam - nie ma przypadkowości.
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}

Stosowanie:

var str = "HELLOWORLD";
var key = R(str.length);
var enc = X(str, key, false);
console.log(enc);
console.log(X(enc,key, true));
wolfhammer
źródło
0

Rubinowy - 184 179 177 znaków

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

Uruchom tak: $ ruby pad-lock.rb

Oto wersja bez golfa, jeśli ktoś jest zainteresowany (nie jest to jednak do tej pory gra w golfa)

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
źródło