{"id":1518,"date":"2021-12-14T09:25:14","date_gmt":"2021-12-14T12:25:14","guid":{"rendered":"http:\/\/localhost\/?page_id=1518"},"modified":"2023-01-06T14:49:23","modified_gmt":"2023-01-06T17:49:23","slug":"criptografia-rsa","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/criptografia-rsa\/","title":{"rendered":"Criptografia RSA"},"content":{"rendered":"
\nNa \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 Ron Rivest<\/a>, Adi Shamir<\/a>, and Leonard Adleman <\/a>e foi publicado em 1977.<\/p>\n

Lembre que a fun\u00e7\u00e3o $\\varphi$ de Euler \u00e9 definida como
\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$ distintos, que
\n\\[
\n\\varphi(pq)=(p-1)(q-1).
\n\\]<\/div>\n

Assuma que Alice quer enviar uma mensagem para Bob. Eles seguem os seguintes passos:<\/p>\n

    \n
  1. Bob escolhe um n\u00famero $n$ tal que $n$ \u00e9 produto de dois primos $p$ e $q$ e escolhe um n\u00famero $e\\in\\{2,\\ldots,n-1\\}$ tal que $\\mbox{mdc}(e,\\varphi(n))=1$. Isso implica que $e$ \u00e9 invert\u00edvel m\u00f3dulo $\\varphi(n)$; ou seja existe $d\\in\\{1,\\ldots,\\varphi(n)\\}$ tal que
    \n\\[
    \ned\\equiv 1\\pmod{\\varphi(n)}.
    \n\\]<\/li>\n
  2. Bob publica o par $(n,e)$ dos n\u00fameros. Este \u00e9 a chave p\u00fablica do Bob e est\u00e1 dispon\u00edvel publicamente para toda pessoa que quer enviar mensagem sigilosa para o Bob. Em particular esta chave \u00e9 conhecida por Alice.<\/li>\n
  3. O Bob guarda os n\u00fameros $(\\varphi(n),d)$ em sigilo. Esta \u00e9 a chave privada do Bob.<\/li>\n
  4. A mensagem da Alice \u00e9 um n\u00famero $b$ entre $1$ e $n$. A Alice vai calcular
    \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
  5. Alice envia $C(b)$ para o Bob.<\/li>\n
  6. Ao receber a mensagem $c=C(b)$ da Alice, Bob calcula
    \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
  7. O n\u00famero $D(c)$ coincide com a mensagem original $b$ da Alice; ou seja, o Bob conseguiu descodificar a mensagem da Alice.<\/li>\n<\/ol>\n
    \nAssuma 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
    \n\\[
    \nde+60k=1
    \n\\]
    \ncom algum $k$ e assim pode ser encontrado usando o Algoritmo de Euclides. De fato, $d=37$. 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 o resto de $D(72)=72^{37}\\equiv 30\\pmod{77}$ que foi a mensagem original da Alice.<\/div>\n

    Vimos no exemplo como o m\u00e9todo funciona, mas queremos entender teoricamente porque ele funciona.<\/p>\n

    \nUsando 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.<\/div>\n
    \nLembre que
    \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 (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

    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 $ed\\equiv 1\\pmod{\\varphi(n)}$, tem-se que
    \n\\[
    \ned=k\\varphi(n)+1=k(p-1)(q-1)+1
    \n\\]
    \ncom algum $k$ inteiro. 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<\/div>\n

    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

    \nConhecendo 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.<\/div>\n
    Assuma que conhecemos o valor de $n$ e $\\varphi(n)$. Primeiro,
    \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$.<\/div>\n

    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> e 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<\/div>\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":1193,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1518"}],"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=1518"}],"version-history":[{"count":5,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1518\/revisions"}],"predecessor-version":[{"id":1998,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1518\/revisions\/1998"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1193"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=1518"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}