Implementar um bloco único

13

fundo

Um bloco de uso único é uma forma de criptografia que se provou impossível de decifrar se usada corretamente.

A criptografia é realizada usando um texto sem formatação (composto apenas de letras AZ) e gerando uma sequência aleatória no mesmo comprimento (também apenas letras). Essa string atua como a chave. Cada caractere no texto simples é então emparelhado com o caractere correspondente na chave. O texto cifrado é calculado da seguinte forma: Para cada par, os dois caracteres são convertidos em números (A = 0, B = 1, ... Z = 25). Os dois números são adicionados ao módulo 26. Esse número é convertido novamente em um caractere.

Descriptografia é exatamente o oposto. Os caracteres no texto cifrado e na chave são emparelhados e convertidos em números. A chave é então subtraída do módulo de texto cifrado 26 e o ​​resultado é convertido novamente em um caractere AZ.

O desafio

Seu desafio é escrever o programa mais curto possível que possa criptografar e descriptografar um bloco único.

Na primeira linha de entrada (para STDIN), haverá a palavra "ENCRYPT" ou a palavra "DECRYPT".

Se a palavra estiver criptografada, a próxima linha será o texto sem formatação. Seu programa deve gerar duas linhas (para STDOUT), sendo a primeira a chave e a segunda o texto cifrado.

Se a palavra for descriptografada, seu programa receberá mais duas linhas de entrada. A primeira linha será a chave e a segunda linha será o texto cifrado. O programa deve gerar uma linha, que será o texto sem formatação que foi descriptografado.

O texto sem formatação, o texto cifrado e a chave devem sempre consistir em letras maiúsculas AZ. Eles sempre serão uma única linha e não conterão espaços em branco.

A chave deve sempre ser aleatória. Nenhuma parte grande dela deve se repetir entre as execuções e não deve haver padrões que possam ser encontrados no texto.

Dois exemplos simples:

ENCRYPT
HAPPYBIRTHDAY
>ABKJAQLRJESMG
>HBZYYRTICLVME

DECRYPT
ABKJAQLRJESMG
HBZYYRTICLVME
>HAPPYBIRTHDAY

O >representa quais linhas são enviadas, assim você não precisa imprimir esse símbolo como saída.

PhiNotPi
fonte
7
Não criticar o desafio por si próprios méritos (que são muito bem), mas eu estou indo para criticar a criptografia aqui. O que você está descrevendo é uma "cifra de fluxo", pois depende de um PRNG (a menos que seu computador tenha acesso a uma fonte ou aleatoriedade real (e se a implementação do linux de / dev / urandom count for assunto de algum debate)) e ter a chave desenvolvida no momento da codificação derrota o único uso realmente bom para um OTP, que é o deslocamento do tempo das comunicações seguras.
dmckee --- gatinho ex-moderador
1
Além disso, como todos os desafios são independentes de idioma, por padrão, removi essa tag.
dmckee --- gatinho ex-moderador
7
@dmckee Em relação ao seu primeiro comentário, eu concordo, e é por isso que não pretendo usar essas respostas para proteger minhas comunicações.
PhiNotPi 16/03/12
1
isso teria sido mais divertido na IMO para deixar a aleatoriedade fora do problema; dada uma fonte de aleatoriedade ( /dev/random, haveged), criptografe xorando as ordens com os bytes e descriptografando-as com a chave. gist.github.com/5078264 a chave ou a aleatoriedade pode ser lida em stdin, a mensagem ou o cyphertext pode ser um argumento de nome de arquivo.
Ixtmixilix 03/03
@PhiNotPi Tenho uma sugestão. Por que não dar um bônus se eles usam uma fonte verdadeiramente aleatório (como /dev/hwrng, em vez de usar pseudo aleatório (que tecnicamente o torna quebrado).
PyRulez

Respostas:

8

GolfScript, 53 caracteres

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

Essa é uma tarefa para a qual o GolfScript parece perfeitamente adequado.

Para manter o código curto, estou usando o mesmo código para criptografia e descriptografia: para descriptografar, subtraio a chave do texto cifrado, enquanto que para criptografia, primeiro gere um texto cifrado aleatório e depois subtraio o texto sem formatação. Mesmo assim, o código extra para implementar o modo de criptografia ocupa pouco mais da metade do tamanho do programa.

Versão descolada com comentários:

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
fonte
4

Ruby ( 200 185)

execuções de amostra + 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
fonte
s[k=(p=f).map{rand 26}],r[k,p,:-]deve ser escritos[k=f.map{rand 26}],r[k,$_,:-]
Hauleth
@ Hauleth não, que não funciona, como $_é apenas a última linha lida por gets. ftambém faz .scan(/./).map{|b|b.ord-65}depois de ler uma linha.
Jsvnm
3

Haskell, 203 caracteres

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

Exemplo:

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

Perl, 220 171 caracteres

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}

Exemplo de execução:

ENCRYPT
HELLO
CCTKK
JGEVY

DECRYPT
CCTKK
JGEVY
HELLO

Nota: pelo menos quando o executo, "Pressione qualquer tecla para continuar ..." é anexado ao final da última saída. Espero que esteja tudo bem, porque não faz parte do programa. Caso contrário, posso fazê-lo aparecer na próxima linha.

Este é o meu primeiro programa real em Perl e o meu primeiro golfe, então eu realmente aprecio dicas. Também encontrei /(.)/gna internet, mas não faço ideia de como funciona (é uma expressão regular? Ainda não as aprendi). Alguém pode me explicar?

EDIT: Obrigado a Ilmari Karonen por me ajudar com os regexps, usei meu novo conhecimento para salvar 7 caracteres!

Versão expandida e ligeiramente legível:

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
}
comando
fonte
Sim, /(.)/gé uma regexp. Você definitivamente vai querer aprender isso se quiser jogar golfe Perl. perldoc.perl.org/perlre.html não é um ponto de partida ruim.
Ilmari Karonen 17/03/12
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)

Acredito que isso atenda exatamente às especificações (inclusive '>'no início dos prompts de entrada.) Ele não valida a entrada, então acho que produzirá apenas saída de lixo se você fornecer caracteres fora de [A-Z]. Ele também verifica apenas a primeira letra do comando de entrada. Qualquer coisa que comece com Dresultará em descriptografia e qualquer outra coisa resultará em criptografia.

Gordon Bailey
fonte
Eu não esperava que você imprimisse >, estava apenas usando-o para demonstrar quais linhas foram produzidas. Você não precisa implementá-las.
PhiNotPi 16/03/12
Ok, legal, 9 caracteres a menos então.
Gordon Bailey
1

C ++ - 220 241 caracteres, 4 linhas

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

Editar 1 - A biblioteca padrão do MSVS parece incluir muitos arquivos desnecessários, o que significava que o ios tinha todas as inclusões necessárias, mas isso não funcionava com outros compiladores. Ios alterados para os arquivos reais em que as funções necessárias aparecem no cstdlib e no cstdio. Agradecemos a Ilmari Karonen por apontar isso.

Scott Logan
fonte
Não compila para mim: g++ otp.cppdizotp.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
Estranho, eu uso o visual studio. Não deve ser padrão para <ios> ter <conio.h> e <stdio.h> em suas inclusões. Presumi que os cabeçalhos sempre incluíam os mesmos arquivos em diferentes implementações. Vou dar uma olhada mais tarde, obrigado.
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

Saída de amostra:

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

Contador de caracteres:

$ wc -c onetimepad.py 
270 onetimepad.py
tomcant
fonte
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
)

Todo o espaço em branco necessário contava.

Versão comentada:

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
fonte
1

C # ( 445 416)

Esqueceu o agregado. Corte um pouco.

Um pouco jogado:

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

}

Golfe:

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
fonte
0

C (159 + 11 para sinalizadores do compilador)

Golfe:

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 com -Dg=gets(s).

Exemplo:

$./onetimepad
ENCRYPT
FOOBAR
>PHQGHU
>UVEHHL
$./onetimepad
DECRYPT
PHQGHU
UVEHHL
>FOOBAR
es1024
fonte
Eu recebo a mesma chave toda vez que a executo - não há aleatoriedade.
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}

Uso:

var str = "HELLOWORLD";
var key = R(str.length);
var enc = X(str, key, false);
console.log(enc);
console.log(X(enc,key, true));
martelo de lobo
fonte
0

Ruby - 184 179 177 caracteres

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

Execute-o assim: $ ruby pad-lock.rb

Aqui está a versão não destruída, se alguém estiver interessado (embora não esteja completamente atualizado com a versão golfada)

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
fonte