{"id":1941,"date":"2022-11-26T08:46:28","date_gmt":"2022-11-26T11:46:28","guid":{"rendered":"http:\/\/localhost\/?page_id=1941"},"modified":"2023-01-06T14:49:36","modified_gmt":"2023-01-06T17:49:36","slug":"um-exempo-computacional-de-rsa","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/um-exempo-computacional-de-rsa\/","title":{"rendered":"Um exempo computacional de RSA"},"content":{"rendered":"
\nNesta p\u00e1gina, vamos realizar uma computa\u00e7\u00e3o em Python para ilustrar o processo de gerar as chaves, criptografar e descriptografar, usando criptografia RSA. Note que a computa\u00e7\u00e3o feita aqui \u00e9 s\u00f3 para ilustrar como combinar os algoritmos estudados neste bloco para criptografia; na pratica, algumas tarefas (tal como a escolha de primos aleat\u00f3rios) devem ser resolvidas com muito mais cuidado.<\/p>\n

Primeiro, precisamos carregar algumas bibliotecas.<\/p>\n

\nfrom sympy import factorint\nimport random\nfrom math import floor, log\n<\/code>\n<\/pre>\n
Vamos precisar das fun\u00e7\u00f5es ExpModN (exponencia\u00e7\u00e3o r\u00e1pida) e XMDC (Algoritmo Estendido de Euclides) que foram definidas em aulas anteriores:<\/p>\n
\ndef ExpModN( a, e, n ):\n    A, P, E = a, 1, e\n        \n    while E != 0:        \n        D = E % 2 # the last binary digit of E         \n        if D == 1:\n            P = (A*P) % n\n            E = (E-1)\/\/2\n        else:\n            E = E\/\/2\n        A = (A*A) % n\n    return P\n<\/code><\/pre>\n
\ndef XMDC(a,b):\n    x0, x = 1, 0; y0, y = 0, 1\n    \n    # n\u00f3s trabalhamos com n\u00fameros positivos, mas aceitamos argumentos negativos\n    sign_a, sign_b = 1, 1\n    if a < 0:\n        a = -a\n        sign_a = -1\n    \n    if b < 0:\n        b = -b\n        sign_b = -1\n    \n    #x0*a + y0*b = a\n    #x*a + y*b = b\n    \n    while b>0: \n        q, r = a \/\/ b, a%b\n        a, b = b, r\n        \n        #atualizar x, x0, y, y0\n        x, x0 = x0 - q*x, x\n        y, y0 = y0 - q*y, y \n    \n    return a, sign_a*x0, sign_b*y0\n\t<\/code><\/pre>\n
O algoritmos de gerar as chaves p\u00fablicas e privadas necessita a computa\u00e7\u00e3o de inverso modular. Isso pode ser feito facilmente usando o algoritmo estendido de Euclides, mas n\u00f3s colocamos aqui uma fun\u00e7\u00e3o que vai resolver esta tarefa:<\/p>\n
\ndef inverso_modular( a, n ):\n    d, u, v = XMDC( a, n )\n    if d != 1:\n        return False\n        \n    u %= n\n    if u < 0:\n        u += n\n    \n    return u\n<\/code><\/pre>\n
Para escolher os primos $p$ e $q$, precisaremos de um teste de primalidade. Usaremos o Teste de Primalidade de Miller. Este teste n\u00e3o \u00e9 deterministico, ter\u00e1 uma probabilidade pequena de erro, mas esta probabilidade pode ser reduzida para um n\u00edvel t\u00e3o baixa que na pr\u00e1tica um n\u00famero que passa por este teste pode ser tratado como primo.<\/p>\n
\ndef IsStrongPseudoPrimeInBase( n, b ):\n    \n    q = n-1\n    k = 0\n    while q % 2 == 0:\n        q = q\/\/2\n        k = k+1\n    \n    r = ExpModN( b, q, n )\n    if r == 1:\n        return True\n    \n    \n    for i in range( 0, k ):\n        if r == n-1:\n            return True\n        r = r*r % n\n        \n    return False\n<\/code><\/pre>\n
\ndef TesteMillerRabin( n, k = 0):\n        \n    if k == 0:\n        k = floor(log( n )) + 1\n        \n    for i in range( k ):\n        b = random.randint( 2, n-2 )\n        if not IsStrongPseudoPrimeInBase( n, b ):\n            return "COMPOSTO"\n        \n    return "PROVAVELMENTE PRIMO"\n<\/code><\/pre>\n
A seguinte fun\u00e7\u00e3o ser\u00e1 usada para escolher um primo aleat\u00f3rio de certo comprimento na base bin\u00e1ria. A ideia, e tomar um n\u00famero aleat\u00f3rio do comprimento desejado, verificar se ele e primo, e se n\u00e3o, aumentar o n\u00famero at\u00e9 obtermos um n\u00famero que \u00e9 (pseudo)primo.<\/p>\n
\ndef primo_aleat\u00f3rio( nr_bits ):\n    \n    p, is_pr = 0, False\n\n   p = random.randint( 2**(nr_bits-1), 2**nr_bits-1 )\n    if p % 2 == 0:\n\t\tp += 1\n\t\n    while True:\n        if TesteMillerRabin( p, 20 ) == "PROVAVELMENTE PRIMO":\n            break\n        p += 2\n        \n    return p\n<\/code><\/pre>\n
Para gerar as chaves p\u00fablicas e privadas, vamos escolher dois primos aleat\u00f3rios $p$ e $q$ tais que o comprimento do produto $n=pq$ \u00e9 2048. Seguimos a recomenda\u00e7\u00e3o que o comprimento de um dos primos seja 40% do comprimento do produto, enquanto o outro contribua com 60% ao comprimento total. Com essa condi\u00e7\u00e3o, a chave ser\u00e1 mais resistente aos ataques para fatorar o produto.<\/p>\n
\np_comp = floor( .4*2048 )\nq_comp = 2048-p_comp\n\np = primo_aleat\u00f3rio( p_comp )\nq = primo_aleat\u00f3rio( q_comp )\nn = p*q\n<\/code><\/pre>\n
Vamos agora computar as chaves $e$ e $d$ usadas para criptografar e descriptografar. A seguinte fun\u00e7\u00e3o vai devolver um n\u00famero aleat\u00f3rio entre $2$ e $n$, invert\u00edvel m\u00f3dulo $\\varphi(n)=(p-1)(q-1)$ junto com seu inverso.<\/p>\n
\ndef key_pair( p, q ):\n    \n\tn, phin = p*q, (p-1)*(q-1)\n    d, e = False, 0\n    while type( d  ) == bool:\n        e = random.randint( 1, n )\n        d = inverso_modular( e, phin )\n    \n    return e, d\n<\/code><\/pre>\n
Rodamos a fun\u00e7\u00e3o que acabamos de definir para gerar as chaves:<\/p>\n
\ne, d = key_pair( p, q )\n<\/code><\/pre>\n
Verifiquemos que $ed\\equiv 1\\pmod{\\varphi(n)}$.<\/p>\n
\ne*d %((p-1)*(q-1))\n1\n<\/code><\/pre>\n
Agora definamos as fun\u00e7\u00f5es de criptografar e descriptografar. Definimos estas fun\u00e7\u00f5es com express\u00f5es-lambda.<\/p>\n
\nC = lambda a: ExpModN( a, e, n )\nD = lambda b: ExpModN( b, d, n )\n<\/code><\/pre>\n
Assuma que a mensagem da Alice \u00e9 um n\u00famero aleat\u00f3rio $a$ entre $1$ e $n$. Alice vai criptografar esta mensagem como $b=C(a)$ e vai enviar ao Bob. Ao receber a mensagem $b$, o Bob vai descriptografar a mensagem da Alice como $c=C(b)$. Pelo que provamos na aula, $c$ coincide com a mensagem original $a$; ou seja $c=a$.<\/p>\n
\na = random.randint( 1, n )\nb = C(a)\nc = D(b)\na == c\n<\/code><\/pre>\n
Para ilustrar a dificuldade de quebrar a criptografia RSA, usaremos a chave usada pelo site ufmg.com em novembro de 2022. O n\u00famero $n$ usada por esta p\u00e1gina pode ser acesso pelas funcionalidades da seguran\u00e7a do browser. A chave aparece como um n\u00famero hexadecimal com o carater “:” separando pares de d\u00edgitos. O seguinte c\u00f3digo transforma este n\u00famero para um n\u00famero inteiro de Python.<\/p>\n
\nn = "C1:D9:49:08:FF:1B:2B:F7:F9:81:E7:EA:CB:21:6B:FC:DA:39:6B:0B:21:8D:A8:19:5F:D5:B3:84:8C:5B:D7:3A:E6:8F:9A:0C:63:AD:F3:FB:BE:27:A7:36:36:3F:24:57:0F:17:68:32:1E:8E:87:92:9E:B7:09:1B:44:81:78:3E:50:1E:A8:BC:D4:E1:83:BB:99:4B:30:66:3F:EB:6D:6A:1F:02:71:02:86:4C:00:D6:F3:6C:3A:61:61:18:21:6F:A8:39:A2:33:B8:31:86:8B:91:FE:F8:69:15:AA:AF:CC:DA:39:8A:E6:13:75:F7:D9:E7:F4:39:C1:35:AF:D5:E7:E1:4C:3E:A6:F2:11:B1:E2:A8:89:29:AE:89:31:1C:E7:F7:89:BF:04:DD:61:02:A1:2D:28:4C:DE:54:62:1E:D5:3C:4A:75:1A:49:24:1E:69:0F:F2:7A:4A:21:4A:57:39:DC:97:68:90:D9:3C:95:55:59:A1:49:3F:E1:D9:07:CE:B6:CE:32:84:0F:F0:F1:7C:A8:78:93:48:69:32:4D:37:7E:4D:96:2E:84:52:90:67:03:AE:F5:31:1C:B0:26:8A:89:BC:01:0B:EA:80:D7:A4:5B:4A:F0:78:0C:AB:E3:A6:A7:88:F1:CD:B9:96:EB:5B:B9:BF:6E:E3:EC:28:A2:CD"\nn = n.replace( ':', '' )\nn = int( n, base = 16 )\n<\/code><\/pre>\n
Agora para quebrar a criptografia, \u00e9 necess\u00e1rio fatorar este n\u00famero. Verificar que o n\u00famero n\u00e3o \u00e9 pseudoprimo para a base $2$ (e ent\u00e3o n\u00e3o \u00e9 primo) \u00e9 f\u00e1cil, mas fatorar \u00e9 dif\u00edcil e de fato n\u00e3o pode ser feito usando as funcionalidades de Python.<\/p>\n
\nIsStrongPseudoPrimeInBase( n, 2 )\nFalse\nfactorint( n )\n...n\u00e3o h\u00e1 resposta...\n<\/code><\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Nesta p\u00e1gina, vamos realizar uma computa\u00e7\u00e3o em Python para ilustrar o processo de gerar as chaves, criptografar e descriptografar, usando criptografia RSA. Note que a computa\u00e7\u00e3o feita aqui \u00e9 s\u00f3 para ilustrar como combinar os algoritmos estudados neste bloco para criptografia; na pratica, algumas tarefas (tal como a escolha de primos aleat\u00f3rios) devem ser resolvidas … Continue reading Um exempo computacional de 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\/1941"}],"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=1941"}],"version-history":[{"count":20,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1941\/revisions"}],"predecessor-version":[{"id":1999,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1941\/revisions\/1999"}],"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=1941"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}