Cracking um n bits RSA números módulo

Question

Isso está relacionado à minha post anterior , onde minha única opção era ter um algoritmo RSA que parecia relativamente fraca. Vamos supor que eu quero para codificar um número de 35 bits (de 0 até 34359738367) com um módulo de 36 bits (entre 34359738368 até 68719476735).

http://en.wikipedia.org/wiki/RSA eu puder ver que o meu n é entre 34359738368 68719476735 até um totiente aleatório (de forma a p-1 * q-1). I escolher um d aleatória e e. I codificar um número e mostrar que na UI.

Para efeitos do argumento, vamos supor que um usuário pode ver até 1.000 dessas saídas. ele pode usar alguns algoritmos como Polla de ou algo semelhante para quebrar o meu d, e ou n e, assim, começar a prever novos números? Se assim o quão duro é que vai ser? (Por apenas saber digamos 1000 conjuntos de entradas / saídas)

Como um exemplo (6 saídas considerar como amostra em formato de entrada / saída),

1. 10001621865,31116156015
2. 10001621866,33031668326
3. 10001621867,37351399313
4. 10001621868,06071714212
5. 10001621869,01188523761
6. 10001621870,18341011998

Alguém pode me dizer o que o meu n, d, e estava? (N entre 34359738368 até 68719476735)

Eu simplesmente quero saber como crackable que é, por isso, se você poderia me dar qualquer informação sobre quanto tempo, com que rapidez, quantas saídas é que uma pessoa tem que ver, o que algoritmos se pode usar etc. Vai ser ótimo.

PS: O usuário não vê a "e" como o algoritmo RSA padrão. Ele só pode ver os conjuntos de saída de entrada.

foram adicionados detalhes Eu estou tentando apresentar um seqüencial user-id do db para o usuário. Porque é seqüencial Eu não quero um usuário adivinhar id de outro usuário, fazendo algumas inscrições. Para evitar isso eu tenho que lutar para um esta questão .

Além disso, o valor de n, d e e não é conhecida para o utilizador. O máximo que um usuário pode ver é uma entrada de alguns ouput amostras (por meio de registrar repetidamente)

Aceitar a resposta postado por Accipitridae desde o algoritmo "Jacobi" pode ser usado para quebrar isso em uma questão de poucos segundos. Sem saber n, e ou p.

Answer 1

Um intruso pode imaginar um factor p de n e e modificação (p-1). Cada suposição pode ser verificado tomando uma mensagem m, computação m ^ e da modificação p e, em seguida, comparando com c mod p, onde c é o texto cifrado correspondente. Desde p e e mod (p-1) são talvez 20 bits cada, isso significa que a segurança do sistema não é maior do que 40 bits.

Mas 40 bits é apenas uma muito rudimentar limite superior. Um atacante pode fazer muito melhor. Por exemplo, ele pode adivinhar um fator p. Em seguida, ele calcula os símbolos Jacobi das mensagens e mensagens cifradas. Se uma mensagem m é um resíduo quadrática da modificação p, em seguida, o texto cifrado deve ser um resíduo quadrática da modificação p e vice-versa. Portanto, se essa relação não é satisfeita para uma mensagem / texto cifrado emparelhar ele pode rejeitar a estimativa para p. Ou o atacante pode calcular logaritmos discretos entre mensagem e texto cifrado. Isto dá um candidato muito mais rápido para o e mod (p-1).

Isso deve dar um nível de 20-30 bits de segurança, portanto, requerem alguns segundos para intervalo. Se você estender o seu número de amostras a 20 eu poderia tentar alguns pontos de referência.

Update: Desde que você não me deu 20 amostras para executar uma experiência, eu tive que gerá-los eu mesmo. Com as seguintes amostras

m = 10001621865  c = 31116156015
m = 10001621866  c = 33031668326
m = 10001621867  c = 37351399313
m = 10001621868  c = 6071714212
m = 10001621869  c = 1188523761
m = 10001621870  c = 18341011998
m = 10001621871  c = 7620400191
m = 10001621872  c = 36106912203
m = 10001621873  c = 37615263725
m = 10001621874  c = 7795237418
m = 10001621875  c = 34774459868
m = 10001621876  c = 4555747045
m = 10001621877  c = 33123599635
m = 10001621878  c = 34836418207
m = 10001621879  c = 33962453633
m = 10001621880  c = 6258371439
m = 10001621881  c = 7500991556
m = 10001621882  c = 5071836635
m = 10001621883  c = 911495880
m = 10001621884  c = 39558568485

como entrada, o algoritmo descrito acima achados os fatores 201821 e 206153 em 20ms. Conforme descrito isso não precisa saber e, embora sua escolha de e = 65537 é fácil de adivinhar e pode ser explorada também.

A força da RSA é que ele é baseado na dificuldade de fatorar grandes inteiros. Aqui você remover esta dificuldade eo que resta são todas as fraquezas (ou seja, relações matemáticas) da RSA. A construção de uma cifra de bloco baseado em RSA é uma idéia horrível. Eu realmente não vejo por que você não quer usar uma construção Luby-Rackoff como propus anteriormente.

Answer 2

RSA é vulnerável contra um ataque Chosen-Ciphertext. Ou seja, dizer que nós queremos quebrar y texto cifrado, podemos usar um dos pares de texto cifrado de texto plano para quebrá-lo.

Como a quebrá-lo:

escolher um x0 e y0, em que x0 e y0 é um par em texto cifrado-que tenha sido fornecida.

y1 = y0 * y mod n Y1 é outro dos 1000 mensagens cifradas dada ao utilizador que satisfaz este critério. x1 é a descriptografia de y1, que também é dado, isto significa:

x1 = y1 ^ d mod n (isto tem sido dado a nós, já sabemos x1)

x1 = (y0 * y) ^ d mod n x1 = y0 ^ d * y ^ d ? x0 mod n * x

x1 * x0 ^ -1 = x

x é a descriptografia de y.

Este é, naturalmente, dependente ou não y0 * y mod n produz outro texto cifrado que já temos, e uma vez que tem apenas 1000 desses pares para trabalhar, é improvável, mas não inviável para quebrar. Você apenas tem que escolher seus pares com muito cuidado.

Eu também gostaria de acrescentar que o tamanho de n você está trabalhando com permite uma heurística factoring para encontrar a fatoração principal de n rapidamente. Além disso, RSA é vulnerável a ataques de tempo, mas que pode ser facilmente contrariado.

Com informações acrescentou: Sem saber n, d, ou e, não há absolutamente nenhuma informação fornecida em tudo, que os meios de adivinhação combinações de n, d ou e é tão bom quanto adivinhar o texto original em si. Para encontrar n e e, há pelo menos 43,359,738,367 combinações de n para adivinhar, bem como todas as combinações e poderia ser. Não é fácil para alguém, mesmo com 1000 pares texto cifrado-texto simples para ser capaz de quebrar n e e.

Answer 3

Esta é uma ideia horrível, de 36 bits RSA ?? Por que não simplesmente ir com um bloco ou stream-cifra? Dessa forma, você começa a 1:. Mapeamento 1 e de uma forma mais segura tanto

Uma solução alternativa que recomendam seria a utilização de um hash SHA como UID e armazenar o número sequencial para cada utilizador na base de dados como uma coluna separada.