Primtal

Jeg har en idé til en krypto-ting, jeg gerne vil lave på et tidspunkt. Idéen vil involvere en Diffie-Hellman nøgleudveksling, og jeg tænkte at 8 kilobit måtte være et passende sikkerhedsniveau. Så jeg satte en computer til at udregne alle safe primes i intervallet 2^8192±2^28

Nu hvor jeg alligevel har lavet udregningen tænkte jeg, at jeg lige så godt kunne dele resultatet af den udregning:

2^8192-174922229
2^8192-85089713
2^8192-71186057
2^8192-49930517
2^8192-43644929
2^8192+22410151
2^8192+120387091
2^8192+120747451
2^8192+131543887
2^8192+167334907
2^8192+185723683
2^8192+192164443

Næste overvejelse er om det er nemmest/mest effektivt at bruge 2^8192-43644929 eller 2^8192+22410151 som modulus til Diffie-Hellman.

Update: Jeg er lidt overrasket over at dette indlæg allerede nu dukker op i Google, hvis man søger på et par af ovenstående tal.

kasperd (1) skrev:

Update: Jeg er lidt overrasket over at dette indlæg allerede nu dukker op i Google, hvis man søger på et par af ovenstående tal.

Newz.dk har en utrolig god søge-rating på Google hvis du ligger mærke til det :)

http://peecee.dk/uploads/122013/kasperd.png

PHP-Ekspert Thoroughbreed (2) skrev:

Newz.dk har en utrolig god søge-rating på Google hvis du ligger mærke til det :)

http://peecee.dk/uploads/122013/kasperd.png

prøv samme søgning i incognito. Google ranker slet ikke newz.dk så højt for mig

mfriis (3) skrev:

prøv samme søgning i incognito. Google ranker slet ikke newz.dk så højt for mig

Well, selv duckduckgo smider Newz op på førstepladsen - dog en gammel nyhed, men hvem ved hvornår crawleren har været på Newz.dk :)

http://peecee.dk/uploads/122013/Sk%C3%A6rmbillede_...

kasperd (1) skrev:

Næste overvejelse er om det er nemmest/mest effektivt at bruge 2^8192-43644929 eller 2^8192+22410151 som modulus til Diffie-Hellman.

Hvis der er en forskel vil jeg mene at det sidste er mest effektivt da 99,79% af bits er 0, men det kan selvfølgelig også betyde noget at det første tal er en bit kortere.

Det er muligvis implementationsspecifikt, så du kan jo lige teste det når du har lavet det.

PHP-Ekspert Thoroughbreed (2) skrev:

hvis du ligger mærke til det

Jeg kiggede lige på første resultat i din søgning, hvor jeg bemærkede følgende troll:

http://newz.dk/populaer-krypteringsalgoritme-har-stor-svaghed#14 skrev:

RSA har i årtier udviklet mere end tvivlsom kryptografi .
Måske er det derfor den Amerikanske Regering er så glade for dem ??

Totalt off-topic og uunderbygget påstand. At det så for et par dage siden viste sig at være sandt er bare et af den slags sjove tilfældigheder, man af og til ser.

mfriis (3) skrev:

Google ranker slet ikke newz.dk så højt for mig

Ranking har ikke meget at sige når man søger efter de specifikke tal, for Google kender tilsyneladende ingen anden side, som indeholder den samme liste af tal.

At indlægget ligger øverst på en liste som kunder har et resultat er ikke specielt overraskende. http://www.google.com/search?q=2%5E8192-43644929+2%5E8192%2B22410151

Men at Google allerede har indekseret indlægget indenfor de 10 minutter jeg havde lov til at opdatere det, synes jeg alligevel er lidt imponerende. Der er sket meget siden dengang Google kun kom forbi sites en gang om måneden.

Emil Melgaard (5) skrev:

Hvis der er en forskel vil jeg mene at det sidste er mest effektivt da 99,79% af bits er 0

Det gør en forskel hvor mange 1 bits, der er i eksponenten. Men er der nogen algoritme som kan udnytte at modulus har mange 0 bits? Desuden betragtes optimeringer baseret på 0 bits i eksponenten ofte som sikkerhedshuller, da det lukker op for side-channel angreb. Målinger af tidsforbrug og strømforbrug kan lække informationer om de bits der regnes på. Det er ca. 10 år siden jeg hørte om den slags angreb første gang. Og for 3-4 år siden hørte jeg om en indirekte måde til at måle strømforbrug på, nemlig ved at optage lyden af kondensatorerne.

kasperd (6) skrev:

Det gør en forskel hvor mange 1 bits, der er i eksponenten. Men er der nogen algoritme som kan udnytte at modulus har mange 0 bits?

Modulus bliver bliver normalt implementeret med noget der ligner det her:

a mod n = a - (n * int(a/n)

Og jeg gættede bare på at division (med meget store tal) er nemmere hvis der er mange 0 bits.

Omvendt kan jeg dog også se at det første tal kan være i 256 words mens det andet kræver 257, så det kan være at det betyder mere.

En hurtig test jeg har kørt i C# der laver 1000 modulus operationer med 894^17192+154685203 mod p for hver af de 2 tal giver ikke nogen tydelig indikation af hvad der er mest effektivt, men det kan jo være anderledes i andre implementeringer.

kasperd (6) skrev:

Desuden betragtes optimeringer baseret på 0 bits i eksponenten ofte som sikkerhedshuller, da det lukker op for side-channel angreb.

Det er ikke noget problem i dette tilfælde da de tal vi snakker om er den offentlige del af protokollen.

Emil Melgaard (7) skrev:

Modulus bliver bliver normalt implementeret med noget der ligner det her:

a mod n = a - (n * int(a/n)

Udregning af a / n og a % n udføres normalt samtidigt. Der er ganske naturlige algoritmer til at udregne begge dele. Skal man kun bruge det ene af de to kan man smide nogle af mellemregningerne væk, men det er ikke ret meget hurtigere at udregne det ene af de to tal fremfor at udregne begge to på samme tid.

Men idet n ligger så tæt på en potens af to er der en anden måde at udregne modulus på. Hvis f.eks. n = 2^8192-43644929 så kan a mod n udregnes ved at dele a op i de nederste 8192 bits og alt derover. Bitene derover shiftes så 8192 positioner til venstre, ganges med 43644929 og lægges til.

Emil Melgaard (7) skrev:

Omvendt kan jeg dog også se at det første tal kan være i 256 words mens det andet kræver 257

Jeg havde nu tænkt mig at nøjes med at bruge 1KB på at repræsentere resultatet i begge tilfælde. Sandsynligheden for at lande på et resultat større end 2^8192 er så lille at den kan ignoreres.

Emil Melgaard (7) skrev:

Det er ikke noget problem i dette tilfælde da de tal vi snakker om er den offentlige del af protokollen.

Modulus er offentligt, men eksponenten er ikke. Og eksponenten vil naturligvis være tilfældig, så der må jeg forvente at have et ligeligt forhold mellem 0 og 1 bits.

Hvis nogen har lyst til at undersøge om mine udregninger er rigtige, så har jeg en liste af divisorer som kan udelukke de fleste ikke safe primes i intervallet 2^8192±2^28. Indtil videre har jeg lavet trial division med alle primtal fra 2 til 3388833383333.