Algoritmul puzzle-ului
Această intrare sau secțiune despre subiectul criptografiei nu menționează sursele necesare sau cei prezenți sunt insuficienți . |
În criptografie , algoritmul puzzle este un exemplu instructiv de algoritm criptografic cu cheie publică . Deși este practic ineficient, conține multe dintre ideile de bază ale algoritmilor mai complexi, în special rezolvă problema schimbului de chei , adică permite două persoane să schimbe mesaje secrete chiar dacă nu au mai schimbat niciodată un secret (cheia). Algoritmul a fost propus de Merkle în octombrie 1974 și publicat în 1978
Operațiune
Să presupunem că Alice și Bob vor să comunice într-un mod sigur, la adăpostul Eva, care are acces la canalul de comunicare și, prin urmare, ar putea intercepta schimburile lor de informații. Bob și Alice trebuie să schimbe cheia , dar nu au un canal sigur pentru a face acest lucru. Alice creează puzzle-uri sau creează multe mesaje codate cu un algoritm ușor de forțat (puzzle-ul este o metaforă, este destul de ușor de rezolvat, deoarece este destul de ușor să forțezi mesajul criptat). Bob primește aceste puzzle-uri ( cheia publică ), spune câteva milioane și alege unul la întâmplare. O rezolvă, adică forțează criptarea. În acest moment, Bob citește mesajul conținut în puzzle, care spune ceva de genul acesta: „Eu sunt numărul puzzle-ului x , numărul cheie x este y ”. În acest moment Bob îi spune lui Alice numărul puzzle-ului: x . În acest fel Alice și Bob au o cheie comună: y. Eva, care a interceptat schimbul de puzzle - uri , are și cheia y , dar este amestecată între un milion de alte chei; știe și numărul cheie. În acest moment el ar putea încerca să rezolve toate puzzle-urile până găsește puzzle-ul numărul x , dar numărul puzzle-urilor este ales astfel încât această operațiune să fie calculată prea mult.
Siguranță
Să presupunem că Alice trimite (aproximativ un milion) de puzzle-uri pentru Bob. În medie, Eva pentru a găsi puzzle-ul care conține cheia utilizată între Bob și Alice va trebui să rezolve jumătate din puzzle-uri: . Dacă lui Bob îi trebuie un minut să rezolve un puzzle, Eva va dura un an pentru a rezolva jumătate din el. Deci, în medie, Eva are nevoie de un an pentru a descifra mesajul interceptat.
Metoda nu este considerată suficient de sigură, deoarece timpul pe care îl va lua Evei pentru a găsi cheia crește quadratic în comparație cu cel luat de Bob. Criptografia asimetrică modernă și protocoalele de schimb de chei necesită algoritmi de atac și legitimi cu complexități de calcul care diferă exponențial.
