b'\n_START_ARTICLE_\nFun\xc3\xa7\xc3\xa3o arapuca\n_START_PARAGRAPH_\nFun\xc3\xa7\xc3\xa3o arapuca, eventualmente conhecida tamb\xc3\xa9m como fun\xc3\xa7\xc3\xa3o armadilha ou fun\xc3\xa7\xc3\xa3o al\xc3\xa7ap\xc3\xa3o, s\xc3\xa3o designa\xc3\xa7\xc3\xb5es poss\xc3\xadveis na l\xc3\xadngua portuguesa para uma fun\xc3\xa7\xc3\xa3o que \xc3\xa9 f\xc3\xa1cil de computar em uma dire\xc3\xa7\xc3\xa3o, mas dif\xc3\xadcil de computar na dire\xc3\xa7\xc3\xa3o oposta (achar a inversa) sem uma informa\xc3\xa7\xc3\xa3o especial, chamada de "arapuca". Fun\xc3\xa7\xc3\xb5es arapuca s\xc3\xa3o amplamente usadas em criptografia._NEWLINE_Em termos matem\xc3\xa1tico, se f \xc3\xa9 uma fun\xc3\xa7\xc3\xa3o arapuca, ent\xc3\xa3o existe uma informa\xc3\xa7\xc3\xa3o secreta y, tal que, dado f(x) e y, \xc3\xa9 f\xc3\xa1cil computar x. Considere um cadeado e sua chave. \xc3\x89 trivial mudar o cadeado de aberto para fechado sem usar a chave, apenas empurrando a trava. Abrir o cadeado de maneira f\xc3\xa1cil, no entanto, requer o uso da chave. Aqui a chave \xc3\xa9 a arapuca._NEWLINE_Fun\xc3\xa7\xc3\xb5es arapuca come\xc3\xa7aram a ser bastante usadas na criptografia na metade dos anos 70, com a publica\xc3\xa7\xc3\xa3o de t\xc3\xa9cnicas de encripta\xc3\xa7\xc3\xa3o assim\xc3\xa9trica (chave p\xc3\xbablica) por Diffie, Hellman e Merkle. Na realidade, Diffie e Hellman cunharam o termo (Diffie e Hellman, 1976). Diversas classes de fun\xc3\xa7\xc3\xb5es foram propostas, e rapidamente percebeu-se que fun\xc3\xa7\xc3\xb5es arapuca s\xc3\xa3o mais dif\xc3\xadceis de se encontrar do que era imaginado. Por exemplo, uma sugest\xc3\xa3o foi usar esquemas baseados no problema da soma de subconjuntos. Isso mostrou-se, por\xc3\xa9m, inapropriado._NEWLINE_Em 2004, as melhores candidatas a fun\xc3\xa7\xc3\xb5es arapuca eram as das fam\xc3\xadlias de fun\xc3\xa7\xc3\xb5es do RSA e de Rabin. Ambas s\xc3\xa3o escritas como exponencia\xc3\xa7\xc3\xb5es m\xc3\xb3dulo um n\xc3\xbamero composto, e s\xc3\xa3o relacionadas ao problema da fatora\xc3\xa7\xc3\xa3o em primos._NEWLINE_Fun\xc3\xa7\xc3\xb5es relacionadas \xc3\xa0 dificuldade do problema do logaritmo discreto (tanto m\xc3\xb3dulo um primo como num grupo definido sobre uma curva el\xc3\xadptica) n\xc3\xa3o s\xc3\xa3o conhecidas como fun\xc3\xa7\xc3\xb5es arapuca, porque n\xc3\xa3o existe uma informa\xc3\xa7\xc3\xa3o "arapuca" conhecida sobre o grupo que torne eficiente a computa\xc3\xa7\xc3\xa3o sobre logaritmos discretos. Entretanto, o problema do logaritmo discreto pode ser usado como base para uma arapuca quando os problemas relacionados chamados de problemas computacionais Diffie-Hellman ou variantes decisionais s\xc3\xa3o usados. A vers\xc3\xa3o semanticamente segura do cripto-sistema ElGamal se ap\xc3\xb3ia no problema decisional de Diffie-Hellman. O algoritmo de assinatura digital \xc3\xa9 baseado no problema computacional de Diffie-Hellman num subgrupo de ordem prima._NEWLINE_Uma arapuca, em criptografia, tem o significado bastante espec\xc3\xadfico citado anteriormente, e n\xc3\xa3o deve ser confundida com porta dos fundos (erro muito frequente). Uma porta dos fundos \xc3\xa9 um mecanismo deliberadamente embutido num algoritmo criptogr\xc3\xa1fico ou sistema operacional, que permite por exemplo que um ou mais usu\xc3\xa1rios n\xc3\xa3o autorizados passe por cima da seguran\xc3\xa7a do sistema, de alguma maneira.'