O desafio
Um simples desafio "espião contra espião".
Escreva um programa com as seguintes especificações:
- O programa pode ser escrito em qualquer idioma, mas não deve exceder 512 caracteres (conforme representado em um bloco de código neste site).
- O programa deve aceitar 5 números inteiros de 32 bits assinados como entradas. Pode assumir a forma de uma função que aceita 5 argumentos, uma função que aceita uma única matriz de 5 elementos ou um programa completo que lê 5 números inteiros de qualquer entrada padrão.
- O programa deve gerar um número inteiro de 32 bits assinado.
- O programa deve retornar 1 se e somente se as cinco entradas, interpretadas como uma sequência, corresponderem a uma sequência aritmética específica da escolha do programador, chamada de "chave". A função deve retornar 0 para todas as outras entradas.
Uma sequência aritmética tem a propriedade de que cada elemento sucessivo é igual ao seu predecessor mais alguma constante fixa a
.
Por exemplo, 25 30 35 40 45
é uma sequência aritmética, pois cada elemento da sequência é igual ao seu antecessor mais 5. Da mesma forma, 17 10 3 -4 -11
é uma sequência aritmética, pois cada elemento é igual ao seu antecessor mais -7.
As sequências 1 2 4 8 16
e 3 9 15 6 12
não são sequências aritméticas.
Uma chave pode ser qualquer sequência aritmética de sua escolha, com a única restrição de que sequências que envolvem estouro de número inteiro não sejam permitidas. Ou seja, a sequência deve aumentar estritamente, diminuir estritamente ou ter todos os elementos iguais.
Como exemplo, suponha que você escolha a chave 98021 93880 89739 85598 81457
. Seu programa deve retornar 1 se as entradas (em sequência) corresponderem a esses cinco números e 0, caso contrário.
Observe que os meios para proteger a chave devem ter seu próprio design inovador. Além disso, soluções probabilísticas que podem retornar falsos positivos com qualquer probabilidade diferente de zero não são permitidas. Em particular, não use hashes criptográficos padrão, incluindo funções de biblioteca para hashes criptográficos padrão.
A pontuação
Os envios mais curtos e sem quebra por contagem de caracteres serão declarados vencedores.
Se houver alguma confusão, não hesite em perguntar ou comentar.
O Contra-Desafio
Todos os leitores, incluindo aqueles que enviaram seus próprios programas, são incentivados a "quebrar" as inscrições. Um envio é quebrado quando sua chave é postada na seção de comentários associados. Se um envio persistir por 72 horas sem ser modificado ou quebrado, será considerado "seguro" e qualquer sucesso subsequente no cracking será ignorado por causa do concurso.
Consulte "Isenção de responsabilidade" abaixo para obter detalhes sobre a política atualizada de pontuação de cracking.
Os envios rachados são eliminados da disputa (desde que não sejam "seguros"). Eles não devem ser editados. Se um leitor deseja enviar um novo programa, ele deve fazê-lo em uma resposta separada.
Os crackers com maior pontuação serão declarados vencedores, juntamente com os desenvolvedores dos programas vencedores.
Por favor, não decifre sua própria submissão.
Boa sorte. :)
Entre os melhores
Penúltima classificação (pendente de segurança da inscrição de Dennis 'CJam 49).
Cacifos seguros
- CJam 49, Dennis
- CJam 62, Dennis a salvo
- CJam 91, Dennis a salvo
- Python 156, Maarten Baert em segurança
- Perl 256, seguro chilemagic
- Java 468, Geobits seguro
Bolachas Imparáveis
- Peter Taylor [Ruby 130, Java 342, Mathematica 146 *, Mathematica 72 *, CJam 37]
- Dennis [Pyth 13, Python 86 *, Lua 105 *, GolfScript 116, C 239 *]
- Martin Büttner [Javascript 125, Python 128 *, Ruby 175 *, Ruby 249 *]
- Tyilo [C 459, Javascript 958 *]
- freddieknets [Mathematica 67 *]
- Ilmari Karonen [Python27 182 *]
- nitroso [C 212 *]
* envio não conforme
Isenção de responsabilidade (atualizado às 23h15 EST, 26 de agosto)
Com os problemas de pontuação finalmente atingindo a massa crítica (dado que dois terços dos envios rachados ainda não são compatíveis), classifiquei os principais crackers em termos de número de envios rachados (primário) e número total de caracteres em envios rachados compatíveis (secundário).
Como antes, os envios exatos ruíram, a duração dos envios e seu status de conformidade / não conformidade são todos marcados para que os leitores possam inferir suas próprias classificações se considerarem injustas as novas classificações oficiais.
Peço desculpas por alterar as regras tão tarde no jogo.
Respostas:
CJam, 62 caracteres
O Stack Exchange é propenso a agrupar caracteres não imprimíveis, mas copiar o código dessa pasta e colá -lo no interpretador CJam funciona bem para mim.
Como funciona
Depois de substituir a cadeia Unicode por uma cadeia ASCII, o seguinte código é executado:
Essa abordagem usa o Bivium-B (consulte Análise algébrica de cifras do tipo Trivium ), uma versão enfraquecida da cifra de fluxo Trivium .
O programa usa a sequência de números inteiros como estado inicial, atualiza o estado 434 vezes (354 rodadas atingem a difusão total) e gera 177 bits de saída, comparados com os da sequência correta.
Como o tamanho do estado é precisamente 177 bits, isso deve ser suficiente para identificar exclusivamente o estado inicial.
Exemplo de execução
fonte
CJam, 91 caracteres
O Stack Exchange é propenso a agrupar caracteres não imprimíveis, mas copiar o código dessa pasta e colá -lo no interpretador CJam funciona bem para mim.
Como funciona
Depois de substituir a cadeia Unicode por números inteiros (considerando os dígitos dos caracteres dos números base 65533), o seguinte código é executado:
Como 13 é coprime para o totiente do módulo (o totiente é secreto, então você só precisa confiar em mim), bases diferentes geram resultados diferentes, ou seja, a solução é única.
A menos que alguém possa explorar o pequeno expoente (13), a maneira mais eficiente de quebrar esse bloqueio é fatorar o módulo (consulte o problema RSA ). Eu escolhi um número inteiro de 512 bits para o módulo, que deve suportar 72 horas de tentativas de fatoração.
Exemplo de execução
fonte
found 1740001 rational and 1739328 algebraic entries
; desde então, foram quase 100 horas para processá-las e relatóriossieving in progress b = 46583, 0 complete / 0 batched relations (need 44970493)
.Python - 128
Vamos tentar este:
(Espera que o usuário insira 5 números separados por vírgula, por exemplo
1,2,3,4,5
.)fonte
32416190039,32416190047,32416190055,32416190063,32416190071
Java: 468
A entrada é fornecida como
k(int[5])
. Bails cedo, se não uniformemente espaçados. Caso contrário, é preciso um pouco para descobrir se todos os dez hashes estão corretos. Para números grandes, "um pouco" pode significar dez segundos ou mais, portanto pode dissuadir os crackers.fonte
Java: 342
Aqui está um armário baseado em string que depende da contagem de caracteres de entrada e da entrada específica. A sequência pode ser baseada em referências obscuras da cultura pop. Diverta-se!
Um pouco destroçado:
fonte
-8675309
, delta é5551212
.Python, 147
Edit: versão mais curta com base no comentário de Dennis. Também atualizei a sequência para evitar vazar qualquer informação.
Baseado no problema discreto de logaritmo, que se acredita ser invencível, no entanto, o principal que estou usando é provavelmente pequeno demais para ser seguro (e pode ter outros problemas, não sei). E você pode fazer força bruta, é claro, já que as únicas incógnitas são dois números inteiros de 32 bits.
fonte
c=1
, computandoc=(c<<32)+d
e alterando a constante de acordo.Javascript 125
Este deve ser quebrado rapidamente. Vou seguir com algo mais forte.
fonte
0, 3913, 7826, 11739, 15652
Ruby, 175
Ao contrário do uso de um hash criptográfico ou
srand
, isso é comprovadamente único (o que é uma pequena pista). Toma cinco números via STDIN, delimitado por qualquer caractere ou caracteres que não sejam de dígito, sem nova linha. Saídas para STDOUT.fonte
622238809,1397646693,2173054577,2948462461,3723870345
(meu palpite anterior teve um erro, mas este foi testado). Eu não acho que isso seja válido, porque o último número não cabe em um número inteiro de 32 bits assinado.GolfScript (116 caracteres)
Recebe a entrada como números inteiros separados por espaço.
fonte
-51469355 -37912886 -24356417 -10799948 2756521
Bytes C 459
RESOLVIDO POR Tyilo - LER EDITAR ABAIXO
Precisamos de alguém para escrever uma solução C, não é? Não estou impressionando ninguém, não sou jogador de golfe. Espero que seja um desafio interessante!
Eu não acho que haja uma maneira óbvia de decifrar essa, e espero ansiosamente todas as tentativas! Eu sei que esta solução é única. Ofuscação muito mínima, principalmente para atender aos requisitos de comprimento. Isso pode ser testado simplesmente:
PS Há um significado para
a[0]
como número por si só, e eu gostaria de ver alguém apontar isso nos comentários!EDITAR:
Solução:
6174, 48216, 90258, 132300, 174342
Uma observação sobre o cracking:
Embora esse não seja o método usado (veja os comentários), eu decifrei minha própria cifra com uma força bruta muito fácil. Agora entendo que é de vital importância aumentar os números. O código a seguir pode decifrar qualquer cifra onde
upper_bound
existe um limite superior conhecidoa[0] + a[1] + a[2] + a[3] + a[4]
. O limite superior na cifra acima é457464
, que pode ser derivado do sistema de equaçõesb[]
e de algumas análises do algoritmo. Isso pode ser demonstradob[4] = a[0] + a[1] + a[2] + a[3] + a[4]
.Com
a[0] = 6174
, esse loop interrompeu meu trabalho em pouco menos de um minuto.fonte
6174, 48216, 90258, 132300, 174342
.Mathematica
8067Corrida:
Provavelmente muito fácil de decifrar, também pode ter várias soluções.
Atualização: Golfe aprimorado, fazendo o que Martin Büttner sugeriu. A funcionalidade da função e da tecla não mudou.
fonte
{58871,5592,-47687,-100966,-154245}
NextPrime
poderia retornar valores negativos. Como você achou isso?Python27,
283182Tudo bem, estou muito confiante no meu armário, no entanto, é bastante longo, já que adicionei cálculos 'difíceis de reverter' à entrada, para torná-lo bem - difícil de reverter.
editar: Agradecimentos a colevk pelo golfe adicional. Percebi durante a edição que havia um erro e uma falha no meu algoritmo, talvez tenha mais sorte na próxima vez.
fonte
121174841 121174871 121174901 121174931 121174961
funciona, mas apenas se a lista[1,3,5,7]
da linha 7 for substituída por[1,3,5,7,11]
.Mathematica
142146EDIT : chave não era única, adicionou 4 caracteres, agora é.
(Espaços e novas linhas adicionados para facilitar a leitura, não são contados e não são necessários).
Uso:
fonte
256208
, delta-5
.IntegerDigits
e depois fatorar para obter candidatos para o mandato e delta inicial.NextPrime
; se variarmos por mais ou menos um, pelo menos um deles dará o mesmo primo seguinte.Rachado por @Dennis em 2 horas
Simples para começar - espero que isso seja rapidamente quebrado.
Pitão , 13
Leva entrada separada por vírgula em STDIN.
Execute-o assim (-c significa assumir o programa como argumento da linha de comando):
Corrigido o programa - eu não tinha entendido as especificações.
Esse idioma pode ser esotérico demais para esta competição - se o OP achar isso, eu o removerei.
fonte
1,2,3,4,5
é a chave?97,96,95,94,93
(Eu acabei de matar a minha pontuação de rachaduras.)Lua 105
Eu suspeito que não demorará muito tempo para que seja quebrado, mas aqui vamos nós:
(espaços adicionados para maior clareza, mas não fazem parte da contagem)
fonte
3, 7, 11, 15, 19
ou6, 14, 22, 30, 38
t1==0
sempre queS
estiver aumentando. Além disso, ambas as condições são homogêneas; seS
é uma solução, o mesmo acontecekS
.Perl - 256
Eu tive que colocar muita lógica de manipulação de erros e isso definitivamente pode ser muito mais eficiente. Ele será impresso
1
quando você obtiver os cinco números corretos. Ele vai espero imprimir um0
para tudo o resto (pode haver erros ou nada, eu não sei). Se alguém quiser ajudar a melhorar o código ou jogar mais, fique à vontade para ajudar!Ligue para:
fonte
Ruby - 130
Baseado no registro de mudança de feedback linear. Entradas por argumentos de linha de comando.
Deve ser exclusivo com base na natureza dos LFSRs. Pista: ascendente e tudo positivo.
Dará mais pistas se ninguém resolver isso em breve.
fonte
Ruby, 249
Deve ser divertido. Quem precisa de matemática?
fonte
309, 77347, 154385, 231423, 308461
mas não acho que seja único.103, 232041, 463979, 695917, 927855
e3, 7966741, 15933479, 23900217, 31866955
. E tenho certeza de que existem outras expressões regulares válidas usando+
s adicionais .()
ou semelhante.CJam, 49 caracteres
Experimente online.
Como funciona
O resultado será 1 se, e somente se, o segundo inteiro for um fator do primeiro, que é um produto de dois primos: o correspondente à sequência secreta e o outro que não corresponde a nenhuma sequência válida. Portanto, a solução é única.
Factorizing um número inteiro de 512 bits não é que difícil, mas eu espero que ninguém será capaz de em 72 horas. Minha versão anterior usando um número inteiro de 320 bits foi quebrada .
Exemplo de execução
fonte
Javascript 958
Converte as entradas em vários tipos de dados e executa algumas manipulações relevantes para cada tipo de dados ao longo do caminho. Deve ser facilmente revertido para qualquer pessoa que gaste algum tempo.
fonte
320689, 444121, 567553, 690985, 814417
C, 239 (Rachado por Dennis)
Vá aqui para o meu envio atualizado.
Provavelmente poderia ser jogado um pouco mais a fundo. É certo que eu não tomei tempo para provar que a chave é única (provavelmente não é), mas é definitivamente da ordem de uma colisão de hash. Se você o quebrar, compartilhe seu método :)
fonte
0 0 0 0 0
?C, 212 por Orby - Rachado
https://codegolf.stackexchange.com/a/36810/31064 da Orby possui pelo menos duas chaves:
Orby pediu o método que eu usei para decifrá-lo. A função p verifica se x é primo verificando
x%i==0
todos os i entre 2 e x (embora esteja usando em(x/i)*i==x
vez dex%i==0
) e retorna true se x é um número primo. A função f verifica se todos os a, b, c, d e e são primos. Ele também verifica se o número m, uma concatenação das representações decimais de e, d, c, bec (nessa ordem), é primo. A chave é tal que a, b, c, d, e em são todos primos.Green e Tao (2004) mostram que existem infinitas seqüências aritméticas de números primos para qualquer comprimento k, portanto, precisamos apenas procurar essas seqüências que também satisfaçam m ser primo. Ao demorar muito tempo, sendo delimitado por -9.223372037e + 18 e 9.223372037e + 18, sabemos que, para que a sequência concatenada se ajuste ao longo, os números têm um limite superior de 9999. Portanto, usando um script python para gerar tudo Se as seqüências aritméticas dentro de todos os números primos <10000 e, em seguida, verificando se a concatenação reversa é primordial, podemos encontrar muitas soluções possíveis.
Por alguma razão, criei falsos positivos, mas os dois acima são válidos de acordo com o programa. Além disso, pode haver soluções em que e é negativo e o restante é positivo (p usa o módulo de x), mas não procurei por elas.
As chaves que eu dei são todas sequências aritméticas, mas o script de Orby não parece realmente exigir que as entradas sejam uma sequência aritmética; portanto, também podem haver chaves inválidas.
fonte
MATLAB: aparentemente inválido
Muito simples, você só precisa gerar o número aleatório certo.
Ainda pode haver erros, mas isso não deve ser um problema.
fonte
MATLAB (com caixa de ferramentas simbólica), 173 caracteres
Esta não é uma entrada oficial e não será contabilizada na pontuação de ninguém, mas garantirá seus direitos de se gabar. ;)
A caixa de ferramentas simbólica é necessária apenas para lidar com a subtração de números inteiros grandes.
Forçar brutalmente deve ser um cachorro, mas se você estiver familiarizado com a série, a solução é trivial.
fonte
Python 2 (91)Editar: isso não é permitido porque o argumento da exclusividade é probabilístico. Desisto.
Leva listas de números inteiros como entrada, como
[1,2,3,4,5]
.O loop destina-se a operar sobre as entradas de maneira irritante, deixando uma torre de somas e expoentes. A idéia é como um log discreto, mas com complicação confusa em vez de simplicidade matemática. Talvez a composição do módulo seja uma vulnerabilidade; nesse caso, eu poderia torná-lo algo parecido
7**58+8
.Realmente não sei como provar que minha chave é a única, mas o intervalo de saídas é pelo menos 10 vezes maior que o intervalo de entradas, então provavelmente? Embora talvez apenas uma pequena fração dos resultados potenciais seja possível. Eu sempre poderia aumentar o número de dígitos ao custo de caracteres. Vou deixar você decidir o que é justo.
Feliz quebrando!
fonte
Mathematica - 72
Versão 2 do meu script, com a mesma chave que a destinada à minha versão 1.
Isso basicamente remove números primos negativos para
NextPrime
.Corrida:
fonte
9244115
, delta25
.1073743739, 1073886396, 1074029053, 1074171710, 1074314367
Python, 86 caracteres
Digite os números como
1,2,3,4,5
.fonte
1,0,1,63021563418517255630720,0
.19960211, 31167202, 42374193, 53581184, 64788175
63021563418517255630720
não é um número de 32 bits.Python, 78
(Rachado por Tyilo em 14 minutos)
Diversão!
Ok, ele não é exibido corretamente aqui :(
Espera uma lista de cinco números, por exemplo. [1,2,3,4,5]
fonte
[-481890276, -594823292, -728999970, -887503650, -1073741792]
CJam, 37 caracteres (quebrado)
Experimente online.
Como funciona
Veja minha nova resposta.
Exemplo de execução
fonte
737262825 208413108 3974530688 3445680972 2916831257
funciona, mas não é uma progressão aritmética. Fatorado em 3 horas e 20 minutos. Aparentemente, os números de 512 bits eram possíveis em 72 horas por US $ 75 no EC2 há dois anos, então acho que isso seria seguro.737262825 208413109 -320436607 -849286323 -1378136039
C, 212 (Rachado)
Essa é a mesma ideia da minha submissão anterior , que jogou com mais profundidade, com um bug corrigido que ultrapassava 0,0,0,0,0 (Obrigado a Dennis por apontar o bug). Compile com -std = c99.
fonte
-7 -37 -67 -97 -127
,-157 -127 -97 -67 -37