Criptografia RSA i Sobre Digital: Compartició Segura de Clau Simètrica

Criptografia RSA i Sobre Digital: Cas Pràctic

Descripció del Problema

L’Alícia i en Bruno volen utilitzar la tècnica del sobre digital per compartir una clau simètrica i intercanviar-se missatges. Per fer-ho, utilitzen el criptosistema RSA, on l’Alícia té com a clau pública PKA = (nA, eA) = (46927, 39423), com a clau secreta SKA = (dA) = (26767), i la clau simètrica que vol compartir és k = 13278. La clau pública d'en Bruno és PKB = (nB, eB) = (17583, 3291) i la seva clau secreta és SKB = (dB) = (11371). Les claus públiques estan publicades en un espai accessible per a qualsevol persona.

Preguntes

1. Motiu de l'ús del Sobre Digital i RSA

   Per quin motiu utilitzen el sobre digital en comptes d’intercanviar-se els missatges xifrats utilitzant directament les claus RSA? Per altra banda, per què necessiten utilitzar RSA i no poden utilitzar directament un algorisme de clau simètrica?

2. Passos per a la Compartició de Clau i Intercanvi de Missatges

   En aquest cas, l’Alícia enviarà el missatge amb la clau simètrica k xifrat i signat utilitzant RSA. Per fer la signatura, utilitzarà una funció hash que, d'un valor x escrit com x1x2x3...xn en valors decimals, retorna x1x2xn; per exemple h(12345) = 125. Explica els passos que donen l’Alícia i en Bruno per a la compartició de la clau simètrica, i com poden intercanviar-se missatges amb aquesta clau. Pots fer aquesta explicació indicant quines operacions de xifrar (E()) i desxifrar (D()) s’utilitzen i amb quines claus, sense haver de mostrar les fórmules matemàtiques.

3. Càlculs de Xifrat i Signatura de l'Alícia

   Mostra els càlculs de com l’Alícia crea el missatge xifrat c que conté la clau simètrica i la signatura s.

4. Càlculs de Desxifrat i Verificació d'en Bruno

   Mostra els càlculs de com en Bruno, a partir de (c, s), obté k i verifica la signatura.

5. Atac de Col·lisió amb Funció Hash Dèbil

   La Claudia intercepta els valors (c, s) que l’Alícia envia a en Bruno. Com es pot imaginar, la funció hash proposada no compleix amb la propietat d’estar lliure de col·lisions que ha de tenir tota bona funció hash. Primer, busca un missatge que generi una col·lisió. Després, descriu breument com la Claudia podria enviar un missatge (c', s) a en Bruno fent-se passar per l’Alícia.

6. Error en la Generació de Claus RSA d'en Bruno

   En aquest escenari, la Claudia s’ha adonat que un dels nombres primers triats per en Bruno per calcular n és 3. Quin requeriment a l’hora de generar claus RSA no ha seguit en Bruno?

7. Càlcul de la Clau Privada d'en Bruno per la Claudia

   A causa d'aquest error, la Claudia podrà calcular la clau privada d’en Bruno a partir de la seva clau pública. Explica i calcula com la Claudia trobarà la clau privada d’en Bruno.

Solucions

1. Motiu de l'ús del Sobre Digital i RSA

   El xifrat de missatges directament amb RSA seria molt més lent, ja que és un algorisme de clau asimètrica. Per això, s'utilitza el sobre digital, que combina la seguretat de la criptografia asimètrica per a la distribució de la clau simètrica amb l'eficiència de la criptografia simètrica per al xifrat dels missatges. No podem utilitzar directament l’algorisme de clau simètrica, ja que, prèviament, cal tenir una clau compartida distribuïda per un canal segur. RSA s'utilitza per establir aquesta clau de manera segura.

2. Passos per a la Compartició de Clau i Intercanvi de Missatges

   1. L’Alícia xifra la clau simètrica amb la clau pública d’en Bruno: c = EPKB(k).
   2. L’Alícia calcula la signatura digital utilitzant la seva clau privada sobre el valor hash de la clau simètrica: s = DSKA(h(k)) = DSKA(138).
   3. L’Alícia envia (c, s) a en Bruno per un canal insegur.
   4. En Bruno desxifra el missatge utilitzant la seva clau privada: k = DSKB(c).
   5. En Bruno verifica la signatura digital amb la clau pública de l’Alícia comparant el resultat amb el hash de la clau que acaba d’obtenir: EPKA(s) = 138 ?= h(k). Si h(k) = 138, aleshores en Bruno verifica la signatura.
   6. L’Alícia i en Bruno poden intercanviar-se missatges mitjançant criptografia simètrica: xifrant amb Ek(m) i desxifrant amb Dk(m).

3. Càlculs de Xifrat i Signatura de l'Alícia

   c = EPKB(k) = keB mod nB = 132783291 mod 17583 = 13494.

   s = DSKA(138) = 138dA mod nA = 13826767 mod 46927 = 2326.

4. Càlculs de Desxifrat i Verificació d'en Bruno

   k = DSKB(c) = cdB mod nB = 1349411371 mod 17583 = 13278.

   h(13278) = 138 ?= EPKA(s) = seA mod nA = 232639423 mod 46927 = 138.

   Per tant, la signatura es verifica.

5. Atac de Col·lisió amb Funció Hash Dèbil

   Un missatge que genera una col·lisió és 1308, ja que h(1308) = 138. Per tant, un atacant que tingui accés als valors (c, s) enviats per l’Alícia, podria crear la tupla (c', s'), on c' = EPKB(1308) i s' = s, i podria enganyar en Bruno fent-li creure que el missatge c' ha estat creat per l'Alícia.

6. Error en la Generació de Claus RSA d'en Bruno

   Per calcular n, és necessari triar dos nombres primers, p i q, que siguin grans i de mida semblant. En Bruno no ha seguit el requeriment de triar nombres primers grans, ja que 3 és un nombre molt petit.

7. Càlcul de la Clau Privada d'en Bruno per la Claudia

   En conèixer un dels factors primers (p = 3), la Claudia pot calcular l'altre:

   • n = 17583
   • p = 3
   • q = n / p = 17583 / 3 = 5861

   Després, pot calcular la funció totient d'Euler φ(n):

   • φ(n) = (p-1) * (q-1) = (3-1) * (5861-1) = 2 * 5860 = 11720

   Sabem que la clau privada d és l'invers modular de la clau pública e mòdul φ(n), és a dir, e * d ≡ 1 (mod φ(n)). La clau pública d'en Bruno és eB = 3291.

   Per tant, d = e-1 mod φ(n) = 3291-1 mod 11720 = 11371.

   Així, la Claudia troba la clau privada d'en Bruno: dB = 11371.