În criptologie , rucsacul Naccache-Stern este o caracteristică de trapă introdusă în 1997 de criptologii David Naccache și Jacques Stern . Securitatea acestei construcții se bazează pe o variantă multiplicativă a problemei rucsacului , pentru care nu se cunoaște astăzi un algoritm eficient (în 2018). Cu toate acestea, această construcție nu este considerată competitivă în ceea ce privește schemele standard; interesul său este astfel în principal teoretic.
Considerăm trei algoritmi definiți după cum urmează.
Fie cel de-al zecelea număr prim , începând cu . Algoritmul ia ca intrare un parametru de securitate , alege un număr întreg și un prim astfel încât
p>∏eu=0nupeu.{\ displaystyle p> \ prod _ {i = 0} ^ {n} p_ {i}.} Algoritmul alege apoi un număr întreg mai întâi cu și apoi se întoarce parametrii publice și rădăcini -lea și magaziilor , .Algoritmul ia ca intrare parametrii publici și un mesaj reprezentat ca un șir binar . Se întoarce
vs.=∏eu=0nuveumeumodp.{\ displaystyle c = \ prod _ {i = 0} ^ {n} v_ {i} ^ {m_ {i}} {\ bmod {p}}.}Algoritmul ia ca intrare parametrii publici, un element și un număr întreg . Se întoarce
m=∑eu=0nu2eupeu-1⋅(pgcd(peu,vs.smodp)-1){\ displaystyle m = \ sum _ {i = 0} ^ {n} {\ frac {2 ^ {i}} {p_ {i} -1}} \ cdot \ left (\ operatorname {pgcd} (p_ {i }, c ^ {s} {\ bmod {p}}) - 1 \ dreapta)}Siguranța funcției trapă se bazează pe dificultatea următoarei probleme de rucsac multiplicativ: dată
vs.=∏eu=0nuveumeumodp.{\ displaystyle c = \ prod _ {i = 0} ^ {n} v_ {i} ^ {m_ {i}} {\ bmod {p}}.} găsește-le . Spre deosebire de criptosistemele adiționale bazate pe rucsac, precum Merkle-Hellman , tehnicile euclidiene de reducere a rețelei nu se aplică acestei probleme.Cel mai bun atac generic cunoscut constă în rezolvarea problemei logaritmului discret pentru a găsi de la , care este
considerat dificil pentru un calculator clasic. În contrast, algoritmul cuantic al lui Shor rezolvă în mod eficient această problemă, iar rucsacul Naccache-Stern nu este deci post-cuantic . Mai mult, în prezent (2018), nu există dovezi că rucsacul Naccache-Stern se reduce la logaritmul discret.Cel mai cunoscut atac specific (în 2018) folosește teorema zilei de
naștere pentru a inversa parțial funcția fără a cunoaște capcana, în ipoteza că mesajul are o greutate Hamming foarte mică. Învățarea mai mult decât un număr logaritmic de biți ai mesajului este o problemă deschisă.Lățimea de bandă (dimensiunea mesajului împărțită la dimensiunea lui ) tinde asimptotic spre zero, din cauza
deficitului de numere prime . Acest fenomen poate fi totuși compensat prin adoptarea unei codificări mai bune a mesajelor.Rucsacul Naccache-Stern este determinist și, prin urmare, nu poate garanta securitatea semantică , care este un obstacol în calea construirii unui criptosistem cu cheie publică . Cu toate acestea, este posibil să modificați funcția prin introducerea unui pericol, care elimină acest obstacol.