Filosofia de Engenharia: Adi Shamir

Principais conclusões

• Ele é o “S” de RSA, o primeiro criptossistema de chave pública prático. Junto com Ron Rivest e Leonard Adleman, Adi Shamir coinventou o RSA no MIT em 1977 – descrito publicamente naquele ano e publicado na Communications of the ACM em fevereiro de 1978. O esquema tornou possível cifrar uma mensagem para alguém, e verificar suas assinaturas, sem jamais compartilhar um segredo de antemão, e sua segurança repousa na dificuldade de fatorar números grandes. O trabalho rendeu aos três o Prêmio Turing da ACM de 2002.¹²
• Ele transformou um polinômio em um segredo perfeito. Em 1979, Shamir publicou “How to Share a Secret”, um esquema de limiar que divide um segredo entre n pessoas de modo que quaisquer k delas possam reconstruí-lo e quaisquer k-1 não aprendam absolutamente nada – nem uma pista, nem um estreitamento. Tudo isso é construído a partir de nada além de pontos sobre um polinômio.³
• Ele é um mestre da criptanálise – ataca para defender. Com Eli Biham, no final da década de 1980, Shamir descobriu publicamente a criptanálise diferencial, um método geral para quebrar cifras de bloco, e antes disso já havia quebrado o criptossistema de mochila de Merkle-Hellman. A mesma mente que construiu o RSA passou décadas aprendendo a quebrar coisas, porque, em criptografia, esse é o único modo honesto de saber que um sistema é forte.⁴⁵
• Ele continua convertendo matemática pura em mecanismo prático. Além do RSA e do compartilhamento de segredo, Shamir coinventou a heurística de Fiat-Shamir – uma maneira de transformar uma prova interativa em uma assinatura não interativa usando uma função de hash – além de esquemas de criptografia baseada em identidade e de criptografia visual. Professor no Instituto Weizmann desde 1980, sua carreira é um longo argumento de que a teoria dos números profunda é um conjunto de ferramentas, não um museu.¹⁶

O princípio

“Mais tarde, descobriu-se que a criptanálise diferencial já era conhecida – e mantida em segredo – tanto pela IBM quanto pela Agência de Segurança Nacional.” – sobre a técnica que Biham e Shamir redescobriram abertamente, parafraseando o registro histórico⁴⁵

A maior parte da engenharia constrói em direção a uma demonstração. Você escreve a coisa, você a executa, ela funciona, e o funcionar é a prova. A criptografia recusa esse conforto. Uma cifra que cifra e decifra corretamente não demonstrou nada sobre se é segura – uma cifra quebrada e uma inquebrável se comportam de forma idêntica até que alguém as ataque. Por isso, o campo teve de inventar um padrão de verdade diferente: um sistema é confiável não quando funciona, mas quando pessoas sérias se esforçaram ao máximo para quebrá-lo e fracassaram. A carreira inteira de Shamir é a encarnação desse padrão. Você protege um sistema aprendendo a quebrar sistemas – atacar para defender.⁴

A expressão mais clara disso é que ele faz as duas metades por conta própria. Ele construiu o RSA, a pedra angular da criptografia de chave pública, e construiu o Compartilhamento de Segredo de Shamir, um esquema com segurança teórico-informacional demonstrável.¹³ Mas ele também quebrou o criptossistema de mochila de Merkle-Hellman – um esquema rival de chave pública que parecia seguro e não era – e codescobriu a criptanálise diferencial, um método geral o bastante para ameaçar o próprio Data Encryption Standard.⁴⁵ Não são duas carreiras. São uma só disciplina. O trabalho de construção lhe diz o que é possível; o trabalho de destruição lhe diz o que é real. Um criptógrafo que só constrói está chutando, e a prova mais arrepiante disso veio depois, quando se soube que a IBM e a NSA conheciam a criptanálise diferencial desde meados da década de 1970 e a mantiveram classificada – ou seja, o campo público vinha construindo cifras cego a um ataque que seus adversários já tinham em mãos.⁴⁵

Há uma segunda metade do princípio, mais silenciosa e igualmente estrutural: o poder de transformar uma ideia matemática pura em um mecanismo prático. Compartilhamento de segredo é apenas interpolação polinomial – um fato que todo estudante encontra na álgebra, o de que dois pontos fixam uma reta e três fixam uma parábola. Shamir percebeu que o mesmo fato, lido ao contrário, é uma primitiva de segurança: distribua os pontos, e a curva permanece oculta até que um número suficiente deles se reúna.³ O RSA é apenas exponenciação modular e a dificuldade de fatorar.² A heurística de Fiat-Shamir é apenas substituir o lançamento de moeda de um verificador por um hash.⁶ Encontre a estrutura matemática pura e, então, leia-a como um mecanismo. O gênio raramente está em uma matemática nova – está em enxergar que uma matemática antiga, vista do ângulo certo, já é a coisa que você precisa construir.

Contexto

Adi Shamir nasceu em 6 de julho de 1952, em Tel Aviv, Israel.¹ Concluiu o bacharelado em matemática na Universidade de Tel Aviv em 1973 e, em seguida, mudou-se para o Instituto Weizmann de Ciência para a pós-graduação, obtendo o mestrado em ciência da computação em 1975 e o doutorado em 1977.¹ Seu timing, como o do próprio campo, estava prestes a virar: 1977 foi o ano em que a criptografia de chave pública passou de uma ideia tentadora a um sistema funcional.

Depois do doutorado, ele passou um ano como pesquisador de pós-doutorado na Universidade de Warwick, na Inglaterra, e então foi para o Instituto de Tecnologia de Massachusetts, onde foi membro do quadro de pesquisa de 1977 a 1980.¹ O MIT é onde o RSA aconteceu. Ron Rivest, o criptógrafo, vinha perseguindo um esquema de chave pública inspirado na ideia de Diffie-Hellman de que duas partes poderiam estabelecer sigilo sem um segredo compartilhado; Shamir e Adleman eram seus colaboradores e, crucialmente, seus adversários – Rivest propunha um esquema, e Shamir e Adleman o quebravam, vez após vez, até que um sobreviveu. O que sobreviveu foi o RSA, batizado com as iniciais dos três, publicado em 1977 e na Communications of the ACM em 1978.² (Sem que eles soubessem, o matemático britânico Clifford Cocks, no GCHQ, havia descrito um sistema equivalente em um documento classificado de 1973 que permaneceu secreto até 1997 – mais um caso do campo construindo no escuro enquanto agências de inteligência observavam.)²

Em 1980, Shamir voltou ao Instituto Weizmann, onde tem sido professor no departamento de ciência da computação e matemática aplicada desde então, ocupando mais tarde também uma cátedra como professor convidado na École Normale Supérieure, em Paris.¹ Quase tudo que o define – o compartilhamento de segredo, o ataque às cifras de mochila, a criptanálise diferencial com seu aluno Eli Biham, a heurística de Fiat-Shamir, a criptografia visual com Moni Naor, os ataques de cubo, os dispositivos de fatoração TWIRL e TWINKLE – saiu do Weizmann. Em 2002, a Association for Computing Machinery concedeu a Rivest, Shamir e Adleman o Prêmio Turing, a maior honraria da computação, por suas contribuições à criptografia de chave pública.¹²

O trabalho

Compartilhamento de Segredo de Shamir: uma parábola que guarda um segredo

Comece por aqui, porque é o princípio em sua forma mais pura e mais bela. Suponha que você tenha um segredo – uma chave-mestra, o código de lançamento, a senha de um tesouro – e queira dividi-lo entre cinco depositários de modo que quaisquer três deles, juntos, possam recuperá-lo, mas que dois deles não consigam aprender nada. Você poderia tentar cortar fisicamente a chave em pedaços, mas isso vaza: cada pedaço estreita o palpite. A percepção de Shamir, em 1979, em “How to Share a Secret”, foi a de que os polinômios já resolvem isso exatamente.³

O truque lê de trás para frente um fato do ensino fundamental. Dois pontos determinam uma única reta; três pontos determinam uma única parábola; em geral, k pontos determinam um único polinômio de grau k-1. Então, para compartilhar um segredo entre n pessoas com um limiar de k, você esconde o segredo como o termo constante de um polinômio aleatório de grau (k-1) – o valor da curva em x = 0 – e entrega a cada pessoa um ponto sobre essa curva.³ Quaisquer k delas conseguem interpolar a curva única que passa por seus pontos e ler seu valor em zero. Mas a parte espantosa é a segurança: com apenas k-1 pontos, a curva não é meramente difícil de encontrar – ela é genuinamente indeterminada. Para cada valor possível do segredo, existe exatamente uma curva do grau certo que passa por aqueles pontos e atinge esse valor em zero. Como garante o esquema de Shamir, “o conhecimento de quaisquer k-1 ou menos partes deixa S completamente indeterminado”.³ Menos do que o limiar não revela nada; o limiar revela tudo. Essa fronteira limpa de tudo-ou-nada é o que o torna seguro do ponto de vista teórico-informacional – seguro não porque quebrá-lo é computacionalmente difícil, mas porque a informação simplesmente não está lá.³

Por que isso importa como engenharia: o esquema é o exemplo canônico de Shamir lendo matemática como mecanismo. Ele não inventou a interpolação polinomial – ela tem séculos. Ele percebeu que seu modo de falha – o de que você não consegue recuperar uma curva a partir de poucos pontos – é precisamente uma propriedade de segurança, e que seu modo de sucesso – o de que pontos suficientes a fixam exatamente – é precisamente uma propriedade de recuperação. O mesmo fato, usado nas duas direções, torna-se uma primitiva criptográfica que roda hoje dentro de módulos de segurança de hardware, da custódia de criptomoedas e de autoridades certificadoras. Matemática pura, lida como ferramenta.³

RSA: cifrando para um estranho

O RSA respondeu a uma pergunta que parecia quase paradoxal: como duas pessoas que nunca se encontraram, e que se comunicam apenas por um fio que um adversário escuta, podem trocar segredos? A criptografia clássica exigia uma chave compartilhada estabelecida de antemão – mas você não pode compartilhar uma chave pelo próprio canal que está tentando proteger. O avanço, que Rivest, Shamir e Adleman transformaram em um sistema funcional em 1977, foi a função unidirecional com armadilha (trapdoor one-way function): uma operação fácil de calcular para a frente e inviável de reverter, a menos que você possua uma informação secreta.²

A armadilha do RSA é a fatoração. Você escolhe dois números primos grandes e os multiplica para formar um módulo n; n e um expoente público tornam-se sua chave pública, que você pode publicar para o mundo. Qualquer pessoa pode usá-la para cifrar uma mensagem destinada a você, por meio de exponenciação modular. Mas decifrar exige a chave privada, que só pode ser derivada dos dois primos originais – e recuperar esses primos a partir de seu produto significa fatorar um número muito grande, um problema sem solução eficiente conhecida.² Como diz a formulação, embora seja prático construir as chaves, “quando se dispõe apenas de e e n, é inviável calcular as raízes e-ésimas módulo n”.² Você publica o cadeado; só você tem a chave; e o abismo entre eles é a dificuldade de fatorar.

Vale enunciar com clareza o papel específico de Shamir, porque é o princípio de novo: ele era, ao lado de Adleman, o criptanalista do trio. A história da invenção do RSA é uma história de quebra – Rivest propunha esquemas candidatos, e Shamir e Adleman os atacavam até que apenas um resistisse ao assédio. O esquema sobrevivente era forte precisamente porque havia sobrevivido aos ataques de duas pessoas determinadas a quebrá-lo. O RSA não é um sistema que foi projetado para ser seguro e, depois, torceu-se para que fosse; é um sistema que conquistou essa pretensão sobrevivendo aos próprios autores.²

Atacar para defender: quebrando mochilas e a criptanálise diferencial

Se o RSA mostra Shamir construindo, o próximo conjunto de trabalhos o mostra fazendo o que o campo precisa ainda mais: quebrar. No final da década de 1970, o criptossistema de mochila de Merkle-Hellman era um rival de destaque do RSA, com sua segurança repousando no problema da “soma de subconjuntos”, que é NP-completo e, portanto, parecia formidavelmente difícil. Shamir o quebrou. Ele mostrou que as mochilas específicas que Merkle-Hellman usava não eram o caso geral difícil, mas um caso especial e estruturado que podia ser resolvido com eficiência – demolindo um esquema em que muitos haviam confiado.¹ A lição é uma que a criptografia não para de reaprender: um problema ser difícil em geral não significa que as instâncias que sua cifra de fato usa sejam difíceis. Só o ataque revela a diferença.

Seu trabalho criptanalítico mais influente veio com seu aluno Eli Biham, no final da década de 1980: a criptanálise diferencial, publicada por volta de 1990.⁴⁵ É uma técnica geral que estuda como diferenças entre pares de entradas de uma cifra se propagam até diferenças na saída. Se certas diferenças de entrada levam a certas diferenças de saída com probabilidade não aleatória, esse viés estatístico é uma rachadura – um vazamento de informação sobre a chave – e Biham e Shamir o transformaram em ataques contra uma gama de cifras de bloco, incluindo uma fraqueza teórica no Data Encryption Standard, então a cifra mais importante do mundo.⁴⁵

Então o campo aprendeu algo humilhante. Em 1994, Don Coppersmith revelou que a IBM – que havia projetado o DES na década de 1970 – conhecia a criptanálise diferencial “já em 1974”, que defender-se dela havia sido um objetivo explícito de projeto do DES, e que a NSA havia pressionado para manter a técnica classificada porque “divulgar as considerações de projeto revelaria a técnica da criptanálise diferencial, uma técnica poderosa que poderia ser usada contra muitas cifras”.⁴⁵ As misteriosas constantes internas do DES, por muito tempo suspeitas de esconder uma porta dos fundos, acabaram revelando esconder uma defesa contra um ataque que o público nem sabia existir. O episódio é o argumento mais forte possível em favor do princípio de Shamir. Por duas décadas, a comunidade aberta construiu e confiou em cifras enquanto permanecia cega a um ataque fundamental que os adversários já detinham. A redescoberta pública de Biham e Shamir não enfraqueceu a criptografia – ela a fortaleceu, ao arrastar o ataque para a luz, onde todos podiam projetar defesas contra ele. Atacar para defender, na escala de um campo inteiro.⁴⁵

Fiat-Shamir e a amplitude do conjunto de ferramentas

O mesmo instinto – encontrar a estrutura pura, lê-la como mecanismo – percorre as outras invenções de Shamir. A heurística de Fiat-Shamir, com Amos Fiat, em meados da década de 1980, resolveu um problema prático das provas interativas de conhecimento: tais provas exigem um vai e vem ao vivo, em que um verificador envia um desafio aleatório e um provador responde. Fiat e Shamir perceberam que a única função do verificador era fornecer aleatoriedade imprevisível, e que uma função de hash criptográfica aplicada à própria mensagem do provador poderia fornecer essa aleatoriedade igualmente bem – transformando uma conversa em uma única prova autocontida e não interativa, ou seja, uma assinatura digital.⁶ Essa única transformação sustenta uma grande parcela dos esquemas modernos de assinatura e dos sistemas de conhecimento zero. Ele também propôs a criptografia baseada em identidade (usando a identidade de uma pessoa como sua chave pública), coinventou a criptografia visual com Moni Naor (dividindo uma imagem em transparências que revelam um segredo apenas quando empilhadas – compartilhamento de segredo que você pode ver) e, mais tarde, desenvolveu os ataques de cubo e os dispositivos de fatoração TWIRL e TWINKLE.¹ Em tudo isso, o padrão se mantém: uma peça conhecida de matemática, virada do jeito certo, torna-se uma ferramenta.

O método

Leia ao longo do RSA, do compartilhamento de segredo, das mochilas quebradas, da criptanálise diferencial e do Fiat-Shamir, e os mesmos compromissos se repetem. O método de Shamir é menos um slogan do que um conjunto de hábitos permanentes.

Construa e quebre com as mesmas mãos. O gesto definidor é recusar a divisão de trabalho entre quem constrói sistemas e quem os ataca. Shamir coinventou o RSA e quebrou a mochila de Merkle-Hellman; ele provou a segurança do compartilhamento de segredo e codescobriu a criptanálise diferencial. A lição se transfere para muito além da criptografia: você não entende o que construiu até ter tentado, a sério, derrotá-lo. É a barreira de evidências elevada a um modo de vida – “funciona” não é evidência de segurança; “pessoas sérias tentaram quebrá-lo e não conseguiram” é.²⁴

Confie apenas no que sobrevive ao ataque. Uma cifra que apenas foi projetada com cuidado é uma esperança; uma cifra que resistiu a uma criptanálise concentrada é um fato. A disciplina é tratar o próprio sistema como culpado até ser atacado – supor que há uma rachadura e ir procurá-la, em vez de esperar que um adversário a encontre por você. Esta é a forma criptográfica de “Reflections on Trusting Trust”, de Thompson: a percepção fundadora de que você não pode confiar no que não examinou de modo adversarial, porque a ameaça que você não consegue ver é a que vai te pegar – como provou a história classificada da criptanálise diferencial.⁴⁵

Leia a matemática como mecanismo. As primitivas mais poderosas raramente são matemática nova; são matemática antiga vista de um ângulo novo. A interpolação polinomial vira compartilhamento de segredo; a dificuldade de fatorar vira uma armadilha; uma função de hash vira substituta de um verificador interativo. O hábito é olhar para uma estrutura pura e perguntar não “o que é isto?”, mas “o que isto poderia fazer?” – a mesma economia de meios que torna as primitivas mais fortes também as mais simples, no espírito do produto mínimo digno.³⁶

Prefira a segurança demonstrável onde for possível obtê-la, e a segurança conquistada em todo o resto. O compartilhamento de segredo é seguro do ponto de vista teórico-informacional – nenhum computador, por mais poderoso que seja, consegue extrair o segredo de poucas partes, porque a informação não está presente.³ O RSA é computacionalmente seguro – protegido apenas enquanto a fatoração permanecer difícil. Shamir trabalha nos dois níveis e é preciso sobre qual deles tem em mãos. A disciplina é saber exatamente sobre o que repousa a sua pretensão de segurança, e nunca confundir “ninguém o quebrou ainda” com “ele não pode ser quebrado”. É qualidade é a única variável aplicada à confiança: a única coisa que conta é se a garantia é real.²³

Desconfie do caso especial escondido dentro do caso geral. Quebrar Merkle-Hellman ensinou ao campo que um problema ser NP-completo em geral não diz nada sobre as instâncias específicas que uma cifra de fato usa.¹ O hábito permanente é suspeitar que a versão conveniente e estruturada de um problema difícil – aquela fácil o suficiente para construir um sistema em torno dela – pode ser exatamente a versão fácil de quebrar. O mesmo ceticismo que Leslie Lamport trouxe aos sistemas distribuídos: não confie na propriedade que você presumiu; encontre a condição precisa sob a qual ela de fato se sustenta.

Cadeia de influência

Quem o moldou

Diffie, Hellman e a ideia de chave pública. O RSA foi uma resposta direta à proposta de 1976 de Whitfield Diffie e Martin Hellman de que o sigilo poderia ser estabelecido sem uma chave pré-compartilhada. Diffie-Hellman formulou a pergunta – um criptossistema de chave pública deveria existir – e Rivest, Shamir e Adleman construíram a primeira resposta prática.² (Influência direta)

Ron Rivest e Leonard Adleman. A colaboração do RSA foi genuinamente a seis mãos: Rivest, o proponente incansável; Shamir e Adleman, os quebradores incansáveis. A estrutura adversarial dessa parceria – propor, atacar, repetir – moldou a convicção que Shamir carregaria por toda a vida de que construção e criptanálise são uma só disciplina.² (Influência formativa)

A tradição da teoria dos números. O gesto característico de Shamir – ler a matemática clássica como mecanismo criptográfico – descende da longa tradição que conecta a teoria dos números, a dificuldade de fatorar e a álgebra dos corpos finitos à computação. Seu gênio foi a aplicação dessa matemática, não sua invenção. (Influência formativa)

Quem ele moldou

Eli Biham e a criptanálise moderna. A criptanálise diferencial, desenvolvida com seu aluno Biham, tornou-se uma ferramenta padrão contra a qual todo projetista sério de cifras de bloco precisa agora se defender – ela reformulou o modo como as cifras são construídas, incluindo os critérios de projeto do Advanced Encryption Standard.⁴⁵

O ecossistema inteiro de chave pública. O RSA sustentou décadas de comunicação segura, de assinaturas digitais e de troca de chaves. Toda vez que um navegador estabelece uma conexão segura ou verifica um certificado, ele se apoia sobre a fundação de chave pública que Shamir ajudou a assentar.²

Conhecimento zero e esquemas de assinatura. A heurística de Fiat-Shamir é um cavalo de batalha sob uma vasta gama de assinaturas digitais modernas e de sistemas de prova de conhecimento zero, incluindo os hoje centrais para a criptografia de preservação de privacidade e de blockchain.⁶

O fio condutor

Shamir é a pedra angular da segurança desta série – a figura que torna o resto da pilha confiável. Tim Berners-Lee construiu uma web pensada para todos, mas uma web em que você pode comprar, fazer transações bancárias e falar livremente depende inteiramente da criptografia de chave pública para suas conexões TLS e certificados assinados – ou seja, depende do RSA e do campo que Shamir ajudou a fundar. Thompson e Ritchie nos deram os sistemas sobre os quais rodamos e, em “Reflections on Trusting Trust”, o alerta fundador de que você não pode confiar no que não examinou de modo adversarial – exatamente o instinto sobre o qual Shamir construiu uma carreira. E Leslie Lamport deu aos sistemas distribuídos a disciplina de definir a correção com precisão e prová-la, contra adversários bizantinos que se comportam de modo arbitrário; o compartilhamento de segredo de Shamir é esse mesmo impulso em forma criptográfica, uma primitiva com uma prova, em vez de uma esperança. Onde Berners-Lee diz isto é para todos e Thompson diz não confie em nada que você não construiu, Shamir diz: vou construir para você algo seguro e, depois, vou passar minha vida tentando quebrá-lo – porque essa é a única forma de qualquer um de nós saber que ele é real. (Ponte da série)

O que eu levo disto

A lição que guardo de Shamir é confie apenas no que sobrevive ao ataque. Meu instinto, como o da maioria dos construtores, é tratar código que funciona como prova – os testes passam, a demo roda, manda pra produção. A criptografia proíbe esse conforto, porque um sistema quebrado e um sólido parecem idênticos até que alguém os ataque, e a resposta de Shamir é ser esse alguém primeiro. Ele quebrou as cifras de mochila; ele e Adleman quebraram os esquemas candidatos de Rivest até o RSA sobreviver; ele e Biham quebraram o DES o suficiente para expor o que as agências de inteligência haviam escondido por vinte anos. Então, quando construo algo agora – um fluxo de autenticação, uma fronteira de permissões, um pipeline de dados – procuro vestir o chapéu do atacante antes que um atacante o vista, supor que há uma rachadura e sair à caça dela, em vez de esperar que me avisem. A confiança que importa não é “não consigo ver como isto se quebra”; é “tentei com afinco quebrá-lo e não consegui”.

A segunda lição é que os mecanismos mais poderosos são matemática pura lida do jeito certo. O compartilhamento de segredo me desmontou um pouco quando o entendi pela primeira vez – é apenas o fato escolar de que pontos determinam um polinômio, e ainda assim produz um segredo que é, de forma demonstrável e teórico-informacional, protegido. Shamir não inventou uma matemática mais difícil; ele percebeu que uma matemática que já tinha era, de um ângulo, exatamente uma primitiva de segurança. Isso mudou o modo como olho para as estruturas que já estão à minha frente. O hash que uso para buscas pode ser um compromisso; a redundância que adicionei para confiabilidade pode ser um esquema de limiar; a restrição que tratei como um estorvo pode ser o cadeado. A habilidade nem sempre está em inventar algo novo – está em reconhecer que a coisa pura que você já entende é, virada do jeito certo, o mecanismo de que você precisava.

Perguntas frequentes

Pelo que Adi Shamir é conhecido?

Adi Shamir é um criptógrafo israelense e professor no Instituto Weizmann de Ciência, mais conhecido como o “S” de RSA – o primeiro criptossistema de chave pública prático, que ele coinventou com Ron Rivest e Leonard Adleman no MIT em 1977. Os três dividiram o Prêmio Turing da ACM de 2002 por esse trabalho. Ele também inventou o Compartilhamento de Segredo de Shamir (1979), codescobriu a criptanálise diferencial com Eli Biham e cocriou a heurística de Fiat-Shamir, entre muitas outras contribuições à criptografia.¹²

O que é o Compartilhamento de Segredo de Shamir?

É um método, publicado por Shamir em 1979 em “How to Share a Secret”, para dividir um segredo entre n pessoas de modo que quaisquer k delas possam reconstruí-lo, mas quaisquer k-1 não aprendam nada. O segredo é escondido como o termo constante de um polinômio aleatório de grau k-1, e cada pessoa recebe um ponto sobre essa curva. Como k pontos determinam de forma única um polinômio de grau (k-1), quaisquer k partes recuperam o segredo – enquanto menos do que k o deixam “completamente indeterminado”, conferindo ao esquema segurança teórico-informacional.³

O que é o “S” de RSA e como o RSA funciona?

O “S” é Shamir; RSA significa Rivest, Shamir e Adleman. O RSA é um criptossistema de chave pública: cada usuário tem uma chave pública que qualquer pessoa pode usar para cifrar mensagens destinadas a ele ou verificar suas assinaturas, e uma chave privada que só ele detém. Sua segurança repousa em uma armadilha – a chave pública é construída a partir do produto de dois números primos grandes, e recuperar a chave privada exige fatorar esse produto de volta em seus primos, o que é computacionalmente inviável para números suficientemente grandes. O RSA foi publicado na Communications of the ACM em 1978.²

O que é a criptanálise diferencial?

A criptanálise diferencial é uma técnica geral, descoberta publicamente por Eli Biham e Adi Shamir no final da década de 1980, para atacar cifras de bloco estudando como as diferenças entre pares de entradas se propagam até diferenças na saída. Vieses estatísticos nessa propagação podem vazar informação sobre a chave secreta; Biham e Shamir a usaram para encontrar uma fraqueza teórica no DES. Mais tarde, descobriu-se que a IBM e a NSA conheciam a técnica desde meados da década de 1970 e a mantiveram classificada, tendo projetado secretamente o DES para resistir a ela.⁴⁵

Fontes