Na \u00e1rea da criptografia, a suposi\u00e7\u00e3o geral \u00e9 que dois parceiros (que podem ser duas pessoas, ou dois computadores) querem trocar informa\u00e7\u00e3o sigilosa usando um canal de comunica\u00e7\u00e3o que est\u00e1 dispon\u00edvel para terceiros. Os dois parceiros geralmente chamam-se A(lice) e B(ob) e um poss\u00edvel terceiro chama-se E(va). Assume-se que as mensagens enviadas por Alice e Bob s\u00e3o n\u00fameros. A Eva consegue interceptar as mensagens enviadas. O objetivo \u00e9 desenvolver m\u00e9todos seguros de codifica\u00e7\u00e3o para as mensagens que podem garantir que Eva n\u00e3o vai conseguir descodificar as mensagens interceptadas.<\/p>\n
Um m\u00e9todo, conhecido como criptografia RSA, foi desenvolvido pelos matem\u00e1ticos\u00a0\u00a0Ron Rivest<\/a>,\u00a0Adi Shamir<\/a>, and\u00a0Leonard Adleman\u00a0<\/a>e foi publicado em 1977.<\/p>\n Exerc\u00edcio.\u00a0<\/strong>Lembre que a fun\u00e7\u00e3o $\\varphi$ de Euler \u00e9 definida como Assuma que Alice quer enviar uma mensagem para Bob. Eles seguem os seguintes passos:<\/p>\n Exemplo.\u00a0<\/strong>Assuma que $n=11\\cdot 7=77$. Neste caso, $\\varphi(n)=10\\cdot 6=60$ e pode-se escolher $e=13$. A chave p\u00fablica de Bob \u00e9 $(77,13)$ e esta chave \u00e9 dispon\u00edvel publicamente. O inverso $d$ de $e$ m\u00f3dulo 60 satisfaz a equa\u00e7\u00e3o Vimos no exemplo como o m\u00e9todo funciona, mas queremos entender teoricamente porque ele funciona.<\/p>\n Teorema.\u00a0<\/strong>Usando a nota\u00e7\u00e3o acima, $D(C(b))=b$ para todo $b\\in\\{1,\\ldots,n-1\\}$. Ou seja, usando a fun\u00e7\u00e3o $D$, o Bob consegue descodificar a mensagem da Alice.<\/p>\n Demonstra\u00e7\u00e3o.<\/strong> Lembre que Primeiro, se $p\\mid b$, ent\u00e3o $p\\mid (b^{ed}-b)$ e a afirma\u00e7\u00e3o \u00e9 verdadeira. Assuma agora que $p\\nmid b$ e lembre que o Pequeno Teorema de Fermat implica neste caso que $b^{p-1}\\equiv 1\\pmod p$. Como\u00a0$ed\\equiv 1\\pmod{\\varphi(n)}$, tem-se que A seguran\u00e7a do m\u00e9todo est\u00e1 baseado no fato que para aplicar a fun\u00e7\u00e3o $D$ de descodifica\u00e7\u00e3o, o Bob precisa calcular o valor de $d$ que precisa do valor de $\\varphi(n)=(p-1)(q-1)$. Claramente, se algu\u00e9m sabe $p$ e $q$ ent\u00e3o consegue calcular $\\varphi(n)$ e tamb\u00e9m a chave privada $d$. Mas a chave p\u00fablica cont\u00e9m o apenas o n\u00famero $n$ e n\u00e3o os seus fatores $p$ e $q$. Neste momento n\u00f3s n\u00e3o conhecemos nenhum algoritmo que pode ser usado para fatorar n\u00fameros muito grandes.<\/p>\n O seguinte resultado implica que a determina\u00e7\u00e3o de $\\varphi(n)$ \u00e9 computacionalmente equivalente \u00e0 determina\u00e7\u00e3o dos fatores $p$ e $q$ de $n$.<\/p>\n Afirma\u00e7\u00e3o.\u00a0<\/strong>Conhecendo o valor de $\\varphi(n)$ (al\u00e9m do valor de $n$), pode-se determinar os primos $p$ e $q$ com uma computa\u00e7\u00e3o eficiente.<\/p>\n Demonstra\u00e7\u00e3o. <\/strong>Assuma que conhecemos o valor de $n$ e $\\varphi(n)$.\u00a0Primeiro, Vale mencionar que existe um algoritmo qu\u00e2ntico eficiente para determinar a fatora\u00e7\u00e3o de um n\u00famero. Este algoritmo \u00e9 conhecido como o Algoritmo de Shor<\/a>\u00a0e foi publicado em 1994. Este algoritmo neste momento n\u00e3o implica nenhum perigo para a seguran\u00e7a de mensagens criptografadas,, mas no futuro os computadores qu\u00e2nticos podem se desenvolver o suficiente para poder quebrar o algoritmo RSA. Neste momento muitos matem\u00e1ticos trabalham no desenvolvimento e algoritmos que s\u00e3o seguros contra ataques de computadores qu\u00e2nticos (criptografia p\u00f3s-qu\u00e2ntica<\/a>).<\/p>\n","protected":false},"excerpt":{"rendered":" Na \u00e1rea da criptografia, a suposi\u00e7\u00e3o geral \u00e9 que dois parceiros (que podem ser duas pessoas, ou dois computadores) querem trocar informa\u00e7\u00e3o sigilosa usando um canal de comunica\u00e7\u00e3o que est\u00e1 dispon\u00edvel para terceiros. Os dois parceiros geralmente chamam-se A(lice) e B(ob) e um poss\u00edvel terceiro chama-se E(va). Assume-se que as mensagens enviadas por Alice e … Continue reading Criptografia RSA<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":706,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1026"}],"collection":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/comments?post=1026"}],"version-history":[{"count":7,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1026\/revisions"}],"predecessor-version":[{"id":1034,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1026\/revisions\/1034"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/706"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=1026"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\\[
\n\\varphi(n)=|\\{a\\in\\{1,\\ldots,n\\}\\mid \\mbox{mdc}(a,n)=1\\}|
\n\\]
\npara todo natural $n$. Demonstra, para primos $p$ e $q$, que $\\varphi(pq)=(p-1)(q-1)$.<\/p>\n\n
\n\\[
\ned\\equiv 1\\pmod{\\varphi(n)}.
\n\\]<\/li>\n
\n\\[
\nC(b)=\\mbox{o resto de $b^e$ por $n$}.
\n\\]
\nNote que Alice conhece os n\u00fameros $e$ e $n$ e consegue calcular $C(b)$ (usando o algoritmo de exponencia\u00e7\u00e3o r\u00e1pida.) O n\u00famero $C(b)$ \u00e9 a mensagem codificada.<\/li>\n
\n\\[
\nD( c)=\\mbox{o resto de $c^d$ m\u00f3dulo $n$}.
\n\\]
\nO n\u00famero obtido $D(c)$ \u00e9 a mensagem descodificada.<\/li>\n
\n\\[
\nde+60k=1
\n\\]
\ncom algum $k$ e assim pode ser encontrado usando o Algoritmo de Euclides. De fato, $d=37$.\u00a0 A mensagem que a Alice manda para o Bob \u00e9 um n\u00famero entre $1$ e $76$. Assuma que a mensagem da Alice \u00e9 o n\u00famero 30. Ent\u00e3o Alice calcula o resto de $30^{13}$ m\u00f3dulo $77$ que d\u00e1 $72$. Ent\u00e3o o mensagem da Alice \u00e9 $C(30)=72$. Ao receber esta mensagem, o Bob calcula\u00a0 o resto de $D(72)=72^{37}\\equiv 30\\pmod{77}$ que foi a mensagem original da Alice.<\/p>\n
\n\\[
\nD(C(b))=(b^e)^d=b^{ed}\\pmod n.
\n\\]
\nPara provar que $D(C(b))=b$, precisa-se verificar que $b^{ed}\\equiv b\\pmod n$; ou seja $n\\mid (b^{ed}-b)$. Como $n=pq$ \u00e9 produto de dois primos, \u00e9 suficiente (e necess\u00e1rio) verificar que $p\\mid\u00a0(b^{ed}-b)$ e $q\\mid (b^{ed}-b)$. N\u00f3s fazemos esta verifica\u00e7\u00e3o para $p$, o primo $q$ pode ser tratado com argumento igual.<\/p>\n
\n\\[
\ned=k\\varphi(n)+1=k(p-1)(q-1)+1
\n\\]
\ncom algum $k$ inteiro.\u00a0 Ent\u00e3o
\n\\[
\nb^{ed}=b^{k(p-1)(q-1)+1}=(b^{p-1})^{k(q-1)}\\cdot b\\equiv b\\pmod p.
\n\\]
\nObtivemos ent\u00e3o que $b^{ed}\\equiv b\\pmod n$ que equivale \u00e0 afirma\u00e7\u00e3o que $D(C(b))=b$ que implica que o m\u00e9todo usado por Bob vai descodificar a mensagem da Alice.<\/p>\n
\n\\[
\n\\varphi(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1
\n\\]
\ne assim conhecemos $p+q=n-\\varphi(n)+1$. Al\u00e9m disso,
\n\\[
\n(p+q)^2-4n=p^2+2pq+q^2-4pq=p^2-2pq+q^2=(p-q)^2
\n\\]
\ne assim
\n\\[
\np-q=\\sqrt{(p+q)^2-4n}.
\n\\]
\nIsto implica, que conseguimos determinar o valor de $p-q$. Sabendo $p+q$ e $p-q$, \u00e9 f\u00e1cil determinar $p$ e $q$.<\/p>\n