{"id":1057,"date":"2020-10-21T17:30:09","date_gmt":"2020-10-21T20:30:09","guid":{"rendered":"http:\/\/localhost\/?page_id=1057"},"modified":"2022-07-04T10:04:57","modified_gmt":"2022-07-04T13:04:57","slug":"assinatura-e-troca-de-chaves","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/algebra-a\/assinatura-e-troca-de-chaves\/","title":{"rendered":"Assinatura e troca de chaves"},"content":{"rendered":"

$\\newcommand{\\Z}{\\mathbb Z}$Vamos estudar dois problemas nesta aula relacionados com criptigrafia:<\/p>\n

    \n
  1. Como enviar uma mensagem criptografada e assinada?<\/li>\n
  2. Como dois parceiros podem gerar uma chave privada comunicando em um canal aberto?<\/li>\n<\/ol>\n

    Assinatura<\/h4>\n

    Assuma que a Alice quer enviar uma mensagem para o Bob. Neste caso \u00e9 importante que o Bob consiga verificar que a mensagem foi enviada pela pr\u00f3pria Alice. Para isso, a Alice precisa assinar a mensagem em alguma forma que a sua assinatura seja verific\u00e1vel.<\/p>\n

    Isso pode ser feito na maneira seguinte:<\/p>\n

      \n
    1. Alice e Bob v\u00e3o escolher suas fun\u00e7\u00f5es de codifica\u00e7\u00e3o e descodifica\u00e7\u00e3o. Assuma que as fun\u00e7\u00f5es da Alice s\u00e3o $C_A$ (codifica\u00e7\u00e3o), $D_A$ (descodifica\u00e7\u00e3o), enquanto as fun\u00e7\u00f5es do Bob s\u00e3o $C_B$ (codifica\u00e7\u00e3o) e $D_B$ (descodifica\u00e7\u00e3o).<\/li>\n
    2. Alice quer enviar uma mensagem $b$ para o Bob a quer assinar a mensagem para seja verific\u00e1vel por Bob que a mesma foi de fato enviada pela Alice. Ent\u00e3o Alice vai criptografar a mensagem calculando $c=C_B(b)$, mas vai enviar tamb\u00e9m a mensagem $a=D_A(b)$ como sua assinatura.<\/li>\n
    3. Ao receber as mensagens\u00a0 $c$ e $a$ da Alice, o Bob descodifica a mensagem $c$ usando sua chave de descodifica\u00e7\u00e3o e obt\u00e9m a mensagem original\u00a0 $b$. Depois o Bob aplica a fun\u00e7\u00e3o de codifica\u00e7\u00e3o $C_A$ da Alice na assinatura e verifica se $C_A(a)=b$. Se sim, ent\u00e3o Bob pode ter certeza que a mensagem foi muito provavelmente enviada pela Alice, pois a assinatura $a$ foi produzida pela chave privada da Alice (desconhecida por todos outros).<\/li>\n<\/ol>\n
      \nNo\u00a0exemplo da aula anterior, a chave p\u00fablica de Bob foi $(77,13)$ e a sua chave privada foi $(60,37)$. Para enviar uma mensagem assinada, Alice tamb\u00e9m vai precisar de um par de chaves e suponha que a chave p\u00fablica da Alice \u00e9 $(143,17)$ (chave p\u00fablica) e a chave privada dela \u00e9 $(120,113)$. A mensagem da Alice \u00e9 o n\u00famero $30$. Alice vai calcular $C_B(30)=30^{13}\\pmod{77}=72$ e vai tamb\u00e9m calcular $D_A(30)=30^{113}\\pmod{143}=127$. Ao receber as mensagens, Bob aplica primeiro a sua fun\u00e7\u00e3o de descodifica\u00e7\u00e3o no primeiro peda\u00e7o da mensagem recebida $D_B(72)=72^{37}\\pmod{77}=30$, mas vai tamb\u00e9m aplicar a fun\u00e7\u00e3o de codifica\u00e7\u00e3o da Alice no segundo peda\u00e7o: $C_A(39)=127^{17}\\pmod{143}=30$. Bob nota que os dois resultados s\u00e3o iguais, ent\u00e3o a mensagem foi de fato enviada por Alice.\n<\/div>\n

      Troca de chaves<\/h4>\n

      Em muitas situa\u00e7\u00f5es os dois parceiros de uma comunica\u00e7\u00e3o secreta precisam escolher uma chave comum para poderem enviar mensagens criptografadas. O problema \u00e9 que eles se comunicam usando um canal aberto, mas querem que a chave escolhida seja sigilosa. O seguinte procedimento \u00e9 conhecido como a Troca de Chaves de Diffie-Hellman. Foi publicada em 1976 e \u00e9 baseado no fato que n\u00e3o conhecemos algoritmo eficiente para o seguinte problema.<\/p>\n

      Problema (logaritmo discreto).\u00a0<\/strong>Seja $p$ um primo e seja $\\bar g$ um elemento primitivo de $\\Z_p$. Dado $\\bar g^k$, determine o n\u00famero $k$.<\/p>\n

      O procedimento de Diffie-Hellman \u00e9 o seguinte:<\/p>\n

        \n
      1. Alice e Bob v\u00e3o escolher um primo $p$ grande e escolhem um elemento primitivo $\\bar g$ em $\\Z_p$. Estes dados n\u00e3o precisam ser sigilosos.<\/li>\n
      2. Alice escolha um inteiro secreto $a\\in\\{1,\\ldots,p-1\\}$ e envia $\\bar x=\\bar g^a$ ao Bob.<\/li>\n
      3. Bob tamb\u00e9m escolha um n\u00famero $b\\in\\{1,\\ldots,p-1\\}$ secreto e envia $\\bar y=\\bar g^b$ \u00e0 Alice.<\/li>\n
      4. Alice vai calcular $\\bar y^a$ e Bob vai calcular $\\bar x^b$. Note que
        \n\\[
        \n\\bar y^a=(\\bar g^b)^a=\\bar g^{ab}=(\\bar g^a)^b=\\bar x^b.
        \n\\]
        \nOu seja, os valores calculados neste passo por Alice e por Bob ser\u00e3o iguais. Este valor comum pode ser usado por Alice e por Bob como um secreto conhecido apenas por eles.<\/li>\n<\/ol>\n

        Note que se Eva interceptar as mensagem comunicadas entre Alice e Bob, ela vai conhecer os valores de $p$, $\\bar g$, $\\bar g^a$ e $\\bar g^b$. Mas para determinar $(\\bar g^a)^b$, ela precisaria do valor de $b$ (ou de $a$), e isso significa resolver o problema de logaritmo discreto.<\/p>\n

        \u00a0Assuma que $p=23$, $\\bar g=5$, $a=10$, $b=20$. Alice vai calcular $\\bar x=\\bar 5^{10}=9$ e manda para o Bob. Bob vai calcular $\\bar y=\\bar 5^{20}=\\overline{12}$. Depois Alice faz $\\overline{12}^{10}=\\bar 2$ enquanto Bob computa $\\bar 9^{20}=\\bar 2$. Depois desta computa\u00e7\u00e3o, os dois obtiveram o mesmo valor $2$ e ele vai ser a chave secreta que eles podem usar para comunicar.\n<\/div>\n","protected":false},"excerpt":{"rendered":"

        $\\newcommand{\\Z}{\\mathbb Z}$Vamos estudar dois problemas nesta aula relacionados com criptigrafia: Como enviar uma mensagem criptografada e assinada? Como dois parceiros podem gerar uma chave privada comunicando em um canal aberto? Assinatura Assuma que a Alice quer enviar uma mensagem para o Bob. Neste caso \u00e9 importante que o Bob consiga verificar que a mensagem foi … Continue reading Assinatura e troca de chaves<\/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\/1057"}],"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=1057"}],"version-history":[{"count":8,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1057\/revisions"}],"predecessor-version":[{"id":1854,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1057\/revisions\/1854"}],"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=1057"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}