b'\n_START_ARTICLE_\nOr\xc3\xa1culo rand\xc3\xb4mico\n_START_PARAGRAPH_\nEm criptografia, um or\xc3\xa1culo rand\xc3\xb4mico \xc3\xa9 um or\xc3\xa1culo (uma caixa-preta te\xc3\xb3rica) que responde para cada consulta \xc3\xbanica com uma resposta (verdadeiramente) rand\xc3\xb4mica, escolhida uniformimente do seu dom\xc3\xadnio de respostas. Se uma consulta \xc3\xa9 repetida, a mesma resposta ser\xc3\xa1 dada para cada consulta submetida._NEWLINE_Dizendo em outras palavras, um or\xc3\xa1culo rand\xc3\xb4mico \xc3\xa9 uma fun\xc3\xa7\xc3\xa3o matem\xc3\xa1tica que mapea cada poss\xc3\xadvel consulta a uma reposta (fixa) rand\xc3\xb4mica do seu dom\xc3\xadnio de sa\xc3\xadda._NEWLINE_Or\xc3\xa1culos rand\xc3\xb4micos como abstra\xc3\xa7\xc3\xb5es matem\xc3\xa1ticas foram primeiramente usados em provas criptogr\xc3\xa1ticas rigorosas no trabalho de Mihir Bellare e Phillip Rogaway (1993).Desde ent\xc3\xa3o, eles s\xc3\xa3o usados tipicamente quando as fun\xc3\xa7\xc3\xb5es criptogr\xc3\xa1ficas de hash n\xc3\xa3o podem ser provadas possuir as propriedades matem\xc3\xa1ticas necess\xc3\xa1rias na prova. Um sistema que \xc3\xa9 provado seguro quando todas as fun\xc3\xa7\xc3\xb5es de hash s\xc3\xa3o substituidas por um or\xc3\xa1culo rand\xc3\xb4mico \xc3\xa9 descrito como sendo seguro no modelo de or\xc3\xa1culo rand\xc3\xb4mico, em oposi\xc3\xa7\xc3\xa3o a seguridade no modelo padr\xc3\xa3o.\n_START_SECTION_\nAplica\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nNa pr\xc3\xa1tica, or\xc3\xa1culos rand\xc3\xb4micos s\xc3\xa3o usados como um substituto ideal para fun\xc3\xa7\xc3\xb5es criptogr\xc3\xa1ficas de hash em esquemas onde fortes premissas sobre aleatoriedade s\xc3\xa3o necess\xc3\xa1rias para a sa\xc3\xadda da fun\xc3\xa7\xc3\xa3o de hash. Tal prova geralmente mostra que um sistema ou protocolo \xc3\xa9 seguro mostrando que um atacante precisa ter um comportamento imposs\xc3\xadvel do or\xc3\xa1culo ou resolver algum problema matem\xc3\xa1tico acreditamento dif\xc3\xadcil, para quebrar o protocolo. Nem todas as fun\xc3\xa7\xc3\xb5es de hash criptogr\xc3\xa1fico requerem or\xc3\xa1culos rand\xc3\xb4micos: Esquemas que requerem apenas algumas propriedades que tem uma defini\xc3\xa7\xc3\xa3o no modelo padr\xc3\xa3o (como resist\xc3\xaancia a colis\xc3\xb5es, resist\xc3\xaancia de imagem reversa, resist\xc3\xaancia de segunda imagem reversa etc) podem, geralmente, ser provados seguros dentro do modelo padr\xc3\xa3o (como o Cripto-Sistema de Cramer-Shoup)._NEWLINE_Or\xc3\xa1culos rand\xc3\xb4micos foram considerados a muito tempo em estudos de complexidade computacional (como, por exemplo, Bennett & Gill), e muitos esquemas foram provados seguros usando o modelo de or\xc3\xa1culo rand\xc3\xb4mico, por exemplo, OAEP, RSA-FDH e PSS. Fiat e Shamir (1986) mostraram uma grande aplica\xc3\xa7\xc3\xa3o de or\xc3\xa1culos rand\xc3\xb4micos - a remo\xc3\xa7\xc3\xa3o de intera\xc3\xa7\xc3\xa3o dos protocolos para cria\xc3\xa7\xc3\xa3o de assinaturas digitais. Impagliazzo e Rudich (1989) mostraram a limita\xc3\xa7\xc3\xa3o de or\xc3\xa1culos rand\xc3\xb4micos - que sua exist\xc3\xaancia, por si, n\xc3\xa3o \xc3\xa9 suficiente para troca de chaves secretas. Bellare e Rogaway em 1993 advogaram seu uso em constru\xc3\xa7\xc3\xb5es criptogr\xc3\xa1ficas. Nesta defini\xc3\xa7\xc3\xa3o, o or\xc3\xa1culo rand\xc3\xb4mico produz uma string de bits de tamanho infinito que pode ser truncada para o tamanho desejado._NEWLINE_Quando um or\xc3\xa1culo rand\xc3\xb4mico \xc3\xa9 usado em uma prova de seguran\xc3\xa7a, ele \xc3\xa9 oferecido a todos os participantes, inclusive os advers\xc3\xa1rios. Um \xc3\xbanico or\xc3\xa1culo pode ser tratado como v\xc3\xa1rios or\xc3\xa1culos, adicionando uma string de bits fixa no in\xc3\xadcio da consulta (por exemplo, consultas formatadas como "1|x" ou "0|x" pode ser consideradas como chamadas para dois or\xc3\xa1culos separados, similarmente, "00|x", "01|x", "10|x" e "11|x" podem ser usadas para representar chamadas a quatro or\xc3\xa1culos separados).\n_START_SECTION_\nLimita\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nNenhuma fun\xc3\xa7\xc3\xa3o comput\xc3\xa1vel por um algoritmo finito pode implementar um or\xc3\xa1culos verdadeiramente rand\xc3\xb4mico (que, por defini\xc3\xa7\xc3\xa3o, requer uma descri\xc3\xa7\xc3\xa3o inifita)._NEWLINE_De fato, certas assinaturas artificiais e esquemas de encripta\xc3\xa7\xc3\xa3o s\xc3\xa3o conhecidos por provarem seguran\xc3\xa7a no modelo de or\xc3\xa1culo rand\xc3\xb4mico, mas s\xc3\xa3o trivialmente inseguros quando qualquer fun\xc3\xa7\xc3\xa3o real \xc3\xa9 usada no lugar no or\xc3\xa1culo rand\xc3\xb4mico. No entanto, para qualquer protocolo natural, uma prova de seguran\xc3\xa7a no modelo de or\xc3\xa1culo rand\xc3\xb4mico \xc3\xa9 uma forte evid\xc3\xaancia de seguran\xc3\xa7a pr\xc3\xa1tica do protocolo._NEWLINE_Em geral, se um protocolo \xc3\xa9 provado seguro, ataques ao protocolo precisam desconsiderar o que foi provado ou quebrar uma das premissas da prova; por exemplo, se uma prova \xc3\xa9 baseada na dificuldade de fatora\xc3\xa7\xc3\xa3o de inteiros, para quebrar essa premissa, o atacante precisa descobrir uma algoritmo de fatoriza\xc3\xa7\xc3\xa3o r\xc3\xa1pido. Em vez disso, para quebrar a premissa do or\xc3\xa1culo rand\xc3\xb4mico, o atacante precisa descobrir alguma propriedade desconhecida ou indesejada na fun\xc3\xa7\xc3\xa3o de hash; para boas fun\xc3\xa7\xc3\xb5es de hash, para as quais tais propriedades s\xc3\xa3o acreditadas inexistentes, o protocolo pode ser considerado seguro.\n_START_SECTION_\nCifra ideal\n_START_PARAGRAPH_\nUma cifra ideal \xc3\xa9 um or\xc3\xa1culo de permuta\xc3\xa7\xc3\xa3o rand\xc3\xb4mica que \xc3\xa9 usado no modelo do cifrador de blocos idealizado. Uma permuta\xc3\xa7\xc3\xa3o rand\xc3\xb4mica decifra para texto cifrado em um, e apenas um, texto e vice-versa, de modo que haja uma correspond\xc3\xaancia um-para-um. Algumas provas criptogr\xc3\xa1ficas permitem n\xc3\xa3o s\xc3\xb3 a permuta\xc3\xa7\xc3\xa3o "direta" para todos os participantes, mas tamb\xc3\xa9m a permuta\xc3\xa7\xc3\xa3o "inversa"._NEWLINE_\xc3\x89 poss\xc3\xadvel construir um cifrador ideal a partir de um or\xc3\xa1culo rand\xc3\xb4mico usando uma Cifra Fiestel de 14 rodadas.'