Que ROT é esse? - descriptografar ROT-n

25

Aqui estão as letras do alfabeto inglês em ordem por frequência:

e t a o i n s h r d l c u m w f g y p b v k j x q z

Ou seja, eé a letra mais usada e zé a menos comum. (Dados da Wikipedia .)

Seu desafio é pegar um texto rotulado como, por exemplo:

ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz

Este é o texto "esta revisão é uma revisão segura e segura" que é "criptografada" através do ROT-21 (metade de 42). Seu programa, usando a tabela de frequência acima, deve poder determinar quanto cada caractere foi rotacionado e o texto original.

(Se você não está familiarizado com o ROT-n, é essencialmente mudar cada caractere n. Por exemplo, no ROT-2,a -> c, b -> d, ..., x -> z, y -> a, z -> b ,.)

Como você pergunta? O algoritmo (muito ingênuo) que você deve usar é:

  • para cada nde 0que 25inclusive, aplicar podridão -npara a cadeia de entrada. (Negativo nporque queremos reverter a criptografia. ROT- -né equivalente a ROT-26-n , se for mais fácil.)
  • converta cada sequência de entrada em um número adicionando as frequências relativas dos caracteres. eé 0, té 1, aé 2, etc. Por exemplo, o número correspondente para a sequência "hello"é 7 + 0 + 10 + 10 + 3 = 30.
  • encontre a string que tem o menor número correspondente.
  • output essa string e seu correspondente n.

Regras:

  • a entrada pode ser em qualquer lugar razoável (STDIN, argumentos da função, de um arquivo etc.), e também a saída (STDOUT, valor de retorno da função para um arquivo etc.)
  • você pode usar um algoritmo diferente, desde que ele sempre produz resultados idênticos. Por exemplo, ter z0 e e25 e escolher o número mais alto também é aceitável.
  • se duas seqüências tiverem pontuações idênticas, você poderá escolher a saída de uma (ou de ambas). Este é um caso extremo e você não precisa prestar contas.
  • isso é , então o código mais curto em bytes vencerá!

Casos de teste:

Entrada: ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz
Saída:21 thisisaverysecretmessagethatisverysecureandsafe

Entrada: pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom
Saída:8 hellopeopleofprogrammingpuzzlescodegolfstackexchange

Entrada: ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq
Saída:12 thiswasencryptedwithrottwelvesoitmustbeperfectlysafe

Entrada: jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv
Saída:2 hereisthefinaltestcasethatyoumustdecrypt

Caso você esteja se perguntando, aqui está um JSFiddle do código de teste JavaScript que eu escrevi, que descriptografou com êxito todos os casos de teste que joguei nele.

Maçaneta da porta
fonte
Pode ser útil observar os casos extremos. Por exemplo, wtaaddeve dar 0 wtaadcomo resultado e vszzcdeve dar 25 wtaadcomo resultado.
mellamokb
Você deve dar pontos extras para detectar a implementação do TrippleROT-N.
User19713
@ user19713 O que é o triplerot? Quero dizer, qual é a diferença entre ROT-6 e três vezes ROT-2?
Lister
2
@mrlister é uma velha piada criptográfica que tira o mijo do TripleDES.
user19713
Podemos gerar o n-root após a string descriptografada?
MayorMonty

Respostas:

6

GolfScript - 87

O truque aqui é construir cada rotação simultaneamente. Como precisamos fazer um loop sobre cada ROT e depois com todos os caracteres, vamos fazer loop com cada caractere, dividir o alfabeto inteiro e depois compactá-lo. A partir daí, proceda conforme o esperado: conte a pontuação para cada ROT e escolha o mínimo.

Golfe extra:

{97- 26,{97+}%.+''+>}/]{27<}%zip:d{{"etaoinshrdlcumwfgypbvkjxqz"?}%{+}*}%.$0=?.26\-\d=

Apenas um pouco de golfe:

# the alphabet, and by frequency
26,{97+}%.+''+:a;
"etaoinshrdlcumwfgypbvkjxqz":f;

# build evey ROT decryption
{97-a>}/]{27<}%zip:d

# calculate likelihood
{{f?}%{+}*}%.

# find min
$0=

# output rotation factor and decryption
?.26\-\d=
couchand
fonte
8

Haskell - 192 175

f y=sum.map(\x->length.fst$break(==x)y)
main=interact(\s->snd$minimum$[(f"etaoinshrdlcumwfgypbvkjxqz"r,show(26-n)++" "++r)|n<-[0..25],let r=map(\x->([x..'z']++['a'..])!!n)s])

Corrida

% ./rot-n <<< "pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom"
8 hellopeopleofprogrammingpuzzlescodegolfstackexchange
swish
fonte
Em vez de somar comprimentos, você pode formar listas representando os números em unário, por exemplo [1,1,1,1], e isso dará a mesma ordem. O mapeamento e a soma tornam-se os concatMapque podem ser escritos de forma sucinta usando uma compreensão da lista. Combinado com alguns outros truques, eu encurtou a 152 caracteres: main=interact(\s->snd$minimum[([1|x<-r,_<-fst$span(/=x)"etaoinshrdlcumwfgypbvkjxqz"],show(26-n)++' ':r)|n<-[0..25],r<-[[([x..'z']++['a'..])!!n|x<-s]]]).
hammar 15/05
7

GolfScript, 112 108 102 100 caracteres

{{}/]{97-}%}:b~:|;"etaoinshrdlcumwfgypbvkjxqz"b:f,:&,{:x[|{&x-+&%f?}%{+}*\]}%$0=1=:x|{&x-+&%97+}%''+

Não estou feliz com a repetição com a decriptografia no final, mas meh.

Ungolfed (se isso faz algum sentido: P) e versão um pouco mais antiga:

# store input IDs (a = 0, b = 1, etc.) in s
[{}/]{97-}%:s;
# store frequency data IDs in f (blah, repetition)
"etaoinshrdlcumwfgypbvkjxqz"[{}/]{97-}%:f

# for each number from 0 to 26 (length of previous string left unpopped)...
,,{
  # the number is x
  :x;
  # return an array of...
  [
    # the score
    s{x 26\-+26%f?}%{+}*
    # and the n
    x
  ]
}%

# use $ort to find the n to output
$0=1=:x

# get the string that the n corresponded to (blah, more repetition)
s{x 26\-+26%97+}%''+
Maçaneta da porta
fonte
"entrada pode ser em qualquer lugar razoável" ajuda o GolfScript. No começo, não conseguia entender por que os dois scripts pareciam imprimir um caractere extra no final, até que percebi que echocoloca uma nova linha por padrão, que o intérprete entende.
couchand
6

JavaScript (205)

f='zqxjkvbpygfwmucldrhsnioate';a='abcdefghijklmnopqrstuvwxyz';for(s=prompt(o=m=n=0)
,i=27;i--;w>m&&(m=w,n=i,o=u))for(u='',w=c=0;c<s.length;w+=f.indexOf(x))u+=x=(a+a)[a
.indexOf(s[c++])+i];alert((26-n)+' '+o)

Eu acho que ainda pode ser jogado um pouco mais, então sugestões são bem-vindas!

Algumas notas para ajudar a entender a solução

  • m, nE oacompanhar a maior pontuação.
  • ue wrastrear o resultado de caractere e valor, respectivamente para o atuali
  • (a+a)ajuda a evitar transbordamentos ao contornar o passado ze é mais curto do que fazer%26
  • Eu tenho a frequência na ordem inversa para que eu possa pesquisar max em vez de min.

Prova: http://jsfiddle.net/J9ZyV/5/

mellamokb
fonte
4

C # + Linq - 273 264

Como uma função que pega a string de entrada e retorna a string decodificada e o deslocamento (conforme os requisitos):

static Tuple<string,int> d(string s){var r=Enumerable.Range(0,25).Select(i=>string.Concat(from c in s select (char)((c-97+i)%26+97))).OrderBy(x=>(from c in x select "etaoinshrdlcumwfgypbvkjxqz".IndexOf(c)).Sum()).First();return Tuple.Create(r,(s[0]-r[0]+26)%26);}

Ungolfed com comentários:

static Tuple<string,int> d(string s)
{
    var r=Enumerable.Range(0,25)                                               // for every possible offset i
          .Select(i=>string.Concat(from c in s select (char)((c-97+i)%26+97))) // calculate rot_i(input string)
          .OrderBy(                                                            // order these by their score
              x=>(
              from c in x select "etaoinshrdlcumwfgypbvkjxqz".IndexOf(c)       // lookup frequency of each character
              ).Sum()                                                          // and sum each frequency to get the score
           ).First();                                                          // get the first one (lowest score)

    return Tuple.Create(r,(s[0]-r[0]+26)%26);                                  // compute offset and return results
}

Pouco driver de teste (lembre-se de compilar referências System.Corepara o Linq):

using System;
using System.Linq;

namespace codegolf
{
    class Program
    {
        static Tuple<string,int> d(string s){var r=Enumerable.Range(0,25).Select(i=>string.Concat(from c in s select (char)((c-97+i)%26+97))).OrderBy(x=>(from c in x select "etaoinshrdlcumwfgypbvkjxqz".IndexOf(c)).Sum()).First();return Tuple.Create(r,(s[0]-r[0]+26)%26);}

        static void Main(string[] args)
        {
            while (true)
            {
                var input = Console.ReadLine();
                if (input == null) break;
                var retval = d(input);
                Console.WriteLine(String.Format("{0} {1}", retval.Item2, retval.Item1));
            }
        }
    }
}

Dando:

$ mcs /reference:System.Core.dll main.cs && mono ./main.exe
ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz
21 thisisaverysecretmessagethatisverysecureandsafe
pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom
8 hellopeopleofprogrammingpuzzlescodegolfstackexchange
ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq
12 thiswasencryptedwithrottwelvesoitmustbeperfectlysafe
jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv
2 hereisthefinaltestcasethatyoumustdecrypt
thisisaverysecretmessagethatisverysecureandsafe
0 thisisaverysecretmessagethatisverysecureandsafe
Thomas
fonte
Acho que você errou a conta - sua solução atual é na verdade 263 caracteres. Além disso, você pode salvar mais um caractere removendo o espaço entreTuple<string,int> d
mellamokb
Aqui está a minha versão, que é muito próxima na implementação, mas um pouco mais curta:Tuple<int,string>f(string x){return Enumerable.Range(0,25).Select(n=>Tuple.Create(26-n,string.Concat(x.Select(c=>(char)((c-97+n)%26+97))))).OrderBy(t=>(t.Item2.Select(c=>"etaoinshrdlcumwfgypbvkjxqz".IndexOf(c))).Sum()).First();}
porges
Eu acho que você deveria estar usando Range(0, 26), não 25.
Rawling 24/03
4

dg - 137 130 129 128 bytes

f=t->min key:(t->sum$map 'etaoinshrdlcumwfgypbvkjxqz'.index$snd t)$map(n->n,''.join$map(c->chr$((ord c + 7-n)%26+ 97))t)(0..26)

Exemplos:

>>> f 'ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz'
(21, 'thisisaverysecretmessagethatisverysecureandsafe')
>>> f 'pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom'
(8, 'hellopeopleofprogrammingpuzzlescodegolfstackexchange')
>>> f 'ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq'
(12, 'thiswasencryptedwithrottwelvesoitmustbeperfectlysafe')
>>> f 'jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv'
(2, 'hereisthefinaltestcasethatyoumustdecrypt')

Código não destruído:

func = t ->
  #: Compute the score of the text `t` with respect to the frequency table.
  #: score :: (int, str) -> int
  score = t ->
    sum $ map 'etaoinshrdlcumwfgypbvkjxqz'.index $ snd t

  #: Compute rot-n of the string `t`. Return the offset and the shifted text.
  #: rot :: int -> (int, str)
  rot = n ->
    n, ''.join $ map (c->chr $ ((ord c + 7 - n) % 26 + 97)) t

  # return the minimum (computed by `score`) amongst all shifted messages
  min key: score $ map rot (0..26)
rubik
fonte
Você não pode remover esses espaços ao redor c - 97e (0..26)?
Mniip 23/03
Só posso remover o segundo. Fazendo isto agora. Vou adicionar alguns exemplos também.
23414 Rubik
1
Nunca ouvi falar dgantes. Você poderia fornecer um link?
TheDoctor 23/03
@TheDoctor: Claro! pyos.github.io/dg é a página inicial e pyos.github.com/dg/tutorial o tutorial.
23414
Você pode salvar um personagem adicionando 7 em vez de subtrair 97. No módulo 26, eles são a mesma coisa.
Hammar
4

J - 92 char

Um patinho feio, mas funciona. Produz o número e a sequência, em duas linhas.

(26|](-1!:2&2&.":)(/:'ctljapqhewvknfdsyigbmuoxrz')+/@i."1(i.<./@:)26|(i.-27)+/])&.(_97+3&u:)

Se você deseja que eles estejam na mesma linha, separados por espaço, isso aumenta apenas 93 caracteres , mas segue uma rota mais feia.

((":@],[:u:32,97+26|-)(/:'ctljapqhewvknfdsyigbmuoxrz')+/@i."1(i.<./@:)26|(i.-27)+/])@(7+3&u:)

Uma explicação para (/:'ctljapqhewvknfdsyigbmuoxrz'): Neste verbo, operamos os valores das letras como A = 0, B = 1, C = 2, etc. Para codificar os valores das letras da sequênciaetaoinshrdlcumwfgypbvkjxqz , o caminho mais curto é realmente levar a permutação de classificação para esta corda estranha. Isso ocorre porque A está no índice 4, B no índice 19, C em 0, D em 14 e assim por diante; portanto, a permutação de classificação é 4 19 0 14 8 13 ...quando você a classifica ( /:) e obtém exatamente os valores numéricos para etaoin....

Uso:

   (26|](-1!:2&2&.":)(/:'ctljapqhewvknfdsyigbmuoxrz')+/@i."1(i.<./@:)26|(i.-27)+/])&.(_97+3&u:) 'ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz'
21
thisisaverysecretmessagethatisverysecureandsafe

   NB. naming for convenience
   f =: (26|](-1!:2&2&.":)(/:'ctljapqhewvknfdsyigbmuoxrz')+/@i."1(i.<./@:)26|(i.-27)+/])&.(_97+3&u:)
   f 'pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom'
8
hellopeopleofprogrammingpuzzlescodegolfstackexchange
   f 'wtaad'
0
wtaad
algoritmshark
fonte
3

q, 97

{(w;m w:g?min g:(+/')("etaoinshrdlcumwfgypbvkjxqz"!t)m:(t!u!/:rotate[;u:.Q.a]'[(-)t:(!)26])@\:x)}

.

q) tests:(
    "ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvazocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz";
    "pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom";
    "ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq";
    "jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv")

q) f:{(w;m w:g?min g:(+/')("etaoinshrdlcumwfgypbvkjxqz"!t)m:(t!u!/:rotate[;u:.Q.a]'[(-)t:(!)26])@\:x)}

q) f each tests
21 "thisisaverysecretmessagethatisverysecureandsafethisisaverysecretmessagethatisverysecureandsafe"
8  "hellopeopleofprogrammingpuzzlescodegolfstackexchange"
12 "thiswasencryptedwithrottwelvesoitmustbeperfectlysafe"
2  "hereisthefinaltestcasethatyoumustdecrypt"
tmartin
fonte
2

APL - 70 caracteres

F←{↑⍋+/'etaoinshrdlcumwfgypbvkjxqz'⍳⊃(⍳26){l[(⍺⌽l←⎕UCS 97+⍳26)⍳⍵]}¨⊂⍵}

Exemplo:

      F 'ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz'
21
      F 'pmttwxmwxtmwnxzwoziuuqvoxchhtmakwlmowtnabiksmfkpivom'
8
      F 'ftueimeqzodkbfqpiuftdaffiqxhqeaufygefnqbqdrqofxkemrq'
12
      F 'jgtgkuvjghkpcnvguvecugvjcvaqwowuvfgetarv'
2

Tenho certeza de que existem maneiras de compactar isso ainda mais e convido outros usuários da APL a encontrar soluções para isso.

Elias Mårtenson
fonte
6
Você tem que enviar a string decidida também ...
Maçaneta da porta
2

Python 188

x="abcdefghijklmnopqrstuvwxyz"
y=input()
r=lambda n:"".join(x[x.find(i)-n]for i in y)
s={sum("etaoinshrdlcumwfgypbvkjxqz".find(b)for b in r(a)):(a,r(a))for a in range(26)}
print(s[min(s)])
gcq
fonte
1

Perl: 256 caracteres (mais novas linhas para facilitar a leitura), incluindo a tabela de frequências:

@f=unpack("W*","etaoinshrdlcumwfgypbvkjxqz");
@c=unpack("W*",<>);$m=ord("a");$b=1E10;
for$n(0..25){$s=0;$t="";
for$x(0..scalar@c){$r=($c[$x]-$n-$m)%26+$m;$t.=chr($r);
for(0..scalar@f){if($r==$f[$_]){$s+=$_}}}
if($s<$b){$b=$s;$w=$t;$a=$n}}
printf"%d %s\n",$a,$w;

O texto é fornecido da seguinte forma:

echo "ocdndnvqzmtnzxmzohznnvbzocvodnqzmtnzxpmzviynvaz" | perl ./freq.pl 
21 thisisaverysecretmessagethatisverysecureandsafewm

Retire 12 caracteres se desejar inserir os valores de ord (a) e o comprimento de @f

OJW
fonte
1

Olmo - 465

Não vai ganhar nenhum prêmio de golfe, mas cria uma página estática que exibe uma lista do formulário [(rotation number, rotated string)]enquanto você digita.

Nota: ainda não está trabalhando aqui, mas você pode copiá-lo e colá-lo no editor oficial e executá-lo.

import String as S
import Char (..)
import Graphics.Input (..)
import Graphics.Input.Field (..)
f="ETAOINSHRDLCUMWFGYPBVKJXQZ"
r s n=let t c=mod(toCode c-65+n)26+65 in map(fromCode . t)(S.toList s)
w s=case s of 
 ""->0
 s->sum(S.indexes(S.left 1 s)f)+w(S.dropLeft 1 s)
b s=sort<|map(\x->((w . S.fromList . r s)x,(26-x,S.fromList<|r s x)))[0..25]
c=input noContent
main=above<~(field defaultStyle c.handle id""<~c.signal)~(asText . b . .string<~c.signal)
hoosierEE
fonte
1

Python 2, 171

f,R,i='zqxjkvbpygfwmucldrhsnioate',{},raw_input();a=sorted(f)*2
for n in range(26):_=''.join(a[ord(x)-71-n]for x in i);R[sum(2**f.index(x)for x in _)]=n,_
print R[max(R)]
dieter
fonte