Misschien kan je je beter inlezen op wat Piekerstoornis inhoudt? Die random links verwijzen nergens dat RSA stuk is ofzo?

Gewoon bullshit - of op z'n best over-geextrapoleerde hype.

Een video presentatie is toch al een tijdverspilling.

Aandacht trekken is gelukt - en misschien ook extra funding trekken ook - maar als je beweert dat je kunt opschalen naar "2048 bit in een paar weken" , kom maar op met een paar 1024 bit factorisaties om te laten zien dat je echt wat kunt.

Terwijl echte resultaten bewijzen op het gebied van factorisatie zo ONTZETTEND SIMPEL is .

Pak gewoon een paar van RSA challenges >1000 bit , en doe het.
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

of (ietwat speciale getallen) https://en.wikipedia.org/wiki/Cunningham_Project

Wat meer leesvoer
https://scottaaronson.blog/?p=2212

Ik heb een beetje heen en weer geklikt - maar ik zag (niet eens) een volledig _resultaat_ van een 300 bit factorisatie, alleen een hoop extrapolities over gevonden relaties.

Misschien miste ik wat, maar als je een 100-cijfer (dat is ca 300 bit) getal echt ontbonden hebt verwacht ik eigenlijk dat je op of de opening of de closing slide inderdaad hebt staan dat

RSA-100 = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139

RSA-100 = 37975227936943673922808872755445627854565536638199
× 40094690950920881030683735292761468389214899724061

(of zo.)
Ik kon zo'n resultaat niet direct vinden .

(btw - dat is nu een paar uur werk op een oude Athlon CPU )

Er is geen certificaat RSA op mijn server actief met Let's Encrypt E1. Althans niet rechtstreeks, wel mogelijk onderliggende certificaten.

Als je client dit anno 2023 op een HTTP client nog niet ondersteunt heb je een groter probleem.

Ook de TS had het hierover, maar TLS- (en eerder SSL-) cipher suites hebben niets met certificaten te maken. De sleutellengtes die je noemt betreffen de lengte van de Diffie-Hellman (wegwerp-) sleutels.

Met de Diffie-Hellman Key Agreement wordt door de client en de server een symmetrische (meestal AES) sessiesleutel overeengekomen zonder dat "meekijkers" die kunnen zien. Echter, de client en de server hebben er geen idee van of de andere partij een AitM is of de bedoelde partij.

Omdat versleutelen onzin is als je niet weet met wie je communiceert (de bedoelde server of een AitM), wordt, bij gebruik van het DH-protocol, een TLS servercertificaat uitsluitend ingezet ter authenticatie van de server (met diens "vaste" private key signeert de server de gebruikte DH-parameters en verstuurt die; de client controleert die digitale handtekening met de public key uit het certificaat, waarmee de in dat certificaat beschreven identiteit van de server aangetoond wordt).

Asymmetrische sleutels kraken: DH of certificaat?
1) Als een aanvaller eerder opgenomen TLS sessies, die met DH zijn beveiligd, wil decrypten, zal zij of hij inderdaad DH-sleutels moeten kraken. Het resultaat is natuurlijk beperkt tot één sessie en is bovendien read-only; als je bijv. bankrekeningen wilt plunderen heb je daar niet zoveel aan.

2) Als je uit de public key in een root- of intermediate-certificaat de bijpassende private key kunt berekenen, kun je zelf valse servercertificaten genereren en daarmee AitM-aanvallen uitvoeren.

Het grootste risico lijkt mij het tweede, omdat je daarmee in één keer veel meer slachtoffers kunt maken.

In beide gevallen moet de aanvaller natuurlijk "toegang hebben tot de verbinding", d.w.z. er "direct" tussen zitten. Denk bijv. aan een fake WiFi accesspoint of andere netwerkapparatuur "onderweg" tussen de client en de server, of de aanvaller moet het netwerkverkeer kunnen omleiden - via een lokale aanval op ARP, DHCP of WPAD, of daarbuiten via een DNS-aanval of BGP-hijack.

RSA wordt gebruikt als handtekeningalgoritme van certificaten en in cipher suites.

Wat je ziet is een check uitgevoerd door SSLLabs (https://www.ssllabs.com/ssltest/analyze.html). Het laat zien dat er geen RSA gebruikt wordt in de suites op mijn server. Het wordt ook niet gebruikt in het EC certificaat.


Dat is het risico van Let's encrypt's E1. De onderliggende certificaten zijn niet allemaal gebaseerd op EC keys maar ook op een RSA keys: https://letsencrypt.org/certificates/

Het bedrijf cpumem heeft het met RSA versleutelde communicatie zonder dat te specificeren. Dat is dus weer een iets andere toepassing van RSA. Ze houden het zo onduidelijk mogelijk. ;)

Het is heel verstandig dat de topic starter een vraagteken heeft geplaatst.
Ik zou overigens wel graag bewijs willen zien dat rsa2k opeens aan diggelen ligt, want geloofwaardig vind ik het niet.

Met alle respect (ook ik heb het moeten leren en moet de ontwikkelingen bijhouden - n.a.v. jouw reactie heb ik mijn geheugen opgefrist en deels moeten corrigeren :-), maar ik denk dat je je wat beter kunt inlezen.

Cipher suites
Voor de leken onder de lezers: je kunt een set (verzameling) van cipher suites vergelijken met de set van talen die een persoon spreekt (een cipher suite staat dus voor één taal, maar kan ook iets over een dialect zeggen, of bijv. En-US versus En-UK - denk bijv. aan "gray" versus "grey", "center" vs "centre" etc).

Stel een Braziliaan en een Bulgaar willen met elkaar een gesprek starten. Als de Bulgaar de initiator is (de client, deze begint met het sturen van een "ClientHello" bericht [0]), stuurt deze een lijstje met talen naar de de Braziliaan (de server) die hij spreekt, bijvoorbeeld Bulgaars, Engels en Duits. Dat lijstje, vergelijkbaar met een lijstje met cipher suites, vergelijkt de Braziliaan (de server) met diens eigen lijst van ondersteunde talen, en zoekt naar overeenkomsten. Als er meerdere overeenkomsten zijn, kiest de server welke gebruikt gaat worden.

[0] https://www.cloudflare.com/learning/ssl/what-happens-in-a-tls-handshake/

RSA
Een RSA sleutelpaar kan ook worden gebruikt voor versleuteling (van een beperkt aantal bytes, vandaar dat er vaak een symmetrische sleutel mee wordt versleuteld).

De term "RSA" in namen van cipher suites kan verwarrend zijn:
1) TLS_RSA_WITH_AES_128_GCM_SHA256 [1]
2) TLS_DHE_RSA_WITH_AES_128_GCM_SHA256 [2]

Bij de eerste wordt RSA zowel voor key exchange als voor authenticatie van de server gebruikt, bij de tweede alleen voor authenticatie (de server bewijst over een private key te beschikken zonder deze prijs te geven).

Bij die eerste werkt het e.e.a. als volgt: de client kiest een symmetrische sessiesleutel, versleutelt die met de RSA public key uit het servercertificaat en stuurt het resultaat naar de server. Als niemand anders dan die server over de bijpassende RSA private key beschikt (en de private key niet uit de public key herleid kan worden, zoals cpumem suggereert), kan alleen die server de symmetrische sessiesleutel decrypten en gebruiken.

Daarmee is de key exchange en authenticatie in één handeling uitgevoerd, en maakt het certificaat (d w.z. het asymmetrische sleutelpaar, met de public key in het certificaat) onderdeel uit van de versleutelingsketen. Bij de tweede cipher suite is de versleuteling volledig onafhankelijk van het certificaat, dat uitsluitend gebruikt wordt voor authenticatie van de server (tevens gebruik maken van een clientcertificaat is ook mogelijk, maar niet erg gebruikelijk bij het verbinden met websites).

[1] Weak: https://ciphersuite.info/cs/TLS_RSA_WITH_AES_128_GCM_SHA256/

[2] Secure: https://ciphersuite.info/cs/TLS_DHE_RSA_WITH_AES_128_GCM_SHA256/

RSA key-exchange
Aangezien de RSA key-exchange werd afgeraden in TLS v1.2 en (als ik het goed begrepen heb) niet meer is toegestaan in TLS v1.3, zie je de letters "RSA" steeds minder vaak in namen van cipher suites.

Het doel van het vervangen van RSA voor de key-exchange is "forward secrecy", waar "ephemeral Diffie-Hellman keys" (éénmalig in te zetten) voor worden gebruikt. Dat is niet omdat dit cryptografisch veiliger is dan RSA, maar om te voorkómen dat opgenomen (versleutelde) sessies later kunnen worden ontsleuteld als de aanvaller de (langdurig gebruikte) RSA private key in handen krijgt.

RSA authenticatie
Bovendien wordt RSA (voor authenticatie) niet meer genoemd in TLS v1.3 ciphers, omdat daar niks over te onderhandelen valt (tijdens elke handshake tussen client en server). Immers, gebruikelijk is dat een TLS server maar één servercertificaat (plus bijpassende private key) heeft, dat minstens 3 maanden geldig is; er valt dus niks te kiezen door clients.

Certificaatkeuze door clients in de toekomst?
Er is overigens wel wat te zeggen voor zo'n protocol: zodra er certificaten verschijnen met een langer dan 4096 bits RSA key of een nu nog ongebruikt (of zelfs nog onbekend) asymmetrisch algoritme, zal er een overgangsperiode zijn waarbij (nog) niet alle webbrowsers dat ondersteunen. Servers zouden dan een oud (mogelijk onveilig) en een nieuw (veiliger) certificaat "aan boord" kunnen hebben, en het oude type alleen verzenden naar browsers die de nieuwe nog niet ondersteunen.

Voorbeeld van allerlei verschillende cipher suites
Een "mooi" voorbeeld van een lange lijst met afschuwelijke cipher suites zag ik zojuist in https://www.ssllabs.com/ssltest/analyze.html?d=fy2023tour.club%2dt.com. De betreffende server (fy2023tour.club-t.com) ondersteunt zelfs de "anon" ciphers "TLS_DH_anon_WITH_AES_128_GCM_SHA256" [3] en "TLS_DH_anon_WITH_AES_256_GCM_SHA384" - waarbij de server niet hoeft te authenticeren (geen certificaat op hoeft te sturen en niet hoeft aan te tonen over de bijpassende private key te beschikken).

[3] Insecure: https://ciphersuite.info/cs/TLS_DH_anon_WITH_AES_128_GCM_SHA256/

Goede achtergrondinfo
Een uitgebreide uitleg van o.a. TLS v1.3, RSA versus DH key exchange en allerlei aanvallen vind je in https://blog.cloudflare.com/rfc-8446-aka-tls-1-3/. M.i. zeer leerzaam, maar uit 2018 dus mogelijk niet meer helemaal up-to-date.

RSA versus ECC
Reken je niet rijk met ECC (Eliptic Curve Cryptography). Uit https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attack (vette opmaak toegevoegd door mij):
Dat zou dus ook zomaar kunnen gelden voor een andere technologie dan quantum computers (zoals ASIC's of Data's Positronic Brain).

Geruchten?
Het verbaast mij niets dat je met ASIC's sneller zou kunnen factoriseren dan met een "gewone" CPU, maar uit niets blijkt dat die snelheidswinst zelfs maar in de buurt komt van wat nodig is om bang te worden. Net zo min verbaast het mij dat een commercieel bedrijfje met onbewezen verzinsels de aandacht probeert te trekken.

11.5 Why do people advise against using RSA-4096?
https://gnupg.org/faq/gnupg-faq.html#please_use_ecc

Robert J. Hansen is een beetje de crypto expert in de gnupg community. Ik vertrouw wat hij zegt.

Waarover zou ik beter moeten inlezen en waarom?

Ik ga voorlopig uit van: https://www.ncsc.nl/documenten/publicaties/2019/mei/01/ict-beveiligingsrichtlijnen-voor-transport-layer-security-tls.

Er zijn heel veel meningen in de cryptowereld en het helpt niet dat inlichtingendiensten invloed proberen uit te oefenen.

Dat is inderdaad een mooie (ssltest output): het lijkt wel of iemand alles heeft aangevinkt onder het idee dat TLS 1.2 wel veilig is :-) Die ga ik gebruiken als voorbeeld bij instructie.
Maar als je DES en RC4 gebruikt snap je het toch niet helemaal. En verbinden met een site waarvan je niet weet wie het is (anon) lijkt me als client ook niet super.
(en best knap: in de moderne standaard builds van OpenSSL zijn die ciphersuites gedisabled: als je de locale opensource kopie van SSLLABS wilt gebruiken (testssl.sh) moet je de juiste openssl library gebruiken omdat anders veel insecure protocollen helemaal niet getest worden!
(de testssl.sh zit standaard in KALI (of is eenvoudig toe te voegen))

Overigens: als je TLS 1.3 actief hebt, zijn dit soort onveilige ciphers niet meer beschikbaar
Dit boek is ook een aanrader: https://www.feistyduck.com/books/bulletproof-tls-and-pki/, ook als je nog niet zo veel weet.
Sowieso is hun newsletter de moeite waard om op te abbonneren

Het verschil in cryptosterkte tussen 112 bit (RSA2048) en 140 bit (RSA4096) is 28 bit, ofwel 2^28 ofwel 268 miljoen keer moeilijker.

De inlichtingen diensten hebben ook behoefte aan goede standaarden, omdat veel kritieke infrastructuur goed beveiliged moet zijn!
Let wel, de standaard waar je nu naar wijst is uit 2019, TLS 1.0 en 1.1, en 3DES zijn bij echt veilige bedrijven allang uitgefaseerd!

Dat is een kant van de medaille.


Dat was in 2019 ook al zo. Er is weinig verandert sindsdien aan TLS. In 2019 gebruikte men nog wel te weinig TLS 1.3. Onder andere Microsoft was er laat mee.

Er is nog geen TLS 1.4 en er was weinig progressie in quantum resistente encryptie (aka PQC). Een paar methoden zijn na introductie afgeschoten als onveilig.

request for comments: https://csrc.nist.gov/Projects/post-quantum-cryptography/news

Als 112 bit 100% is, is 140 bit 125%. Dus in plaats van een verdubbeling, komt er 25% bij.

Nu kost opslag niets en zijn processors ook heel erg snel, dus waarom geen 32K RSA sleutels aanmaken? Ik heb als test net een RSA/RSA sleutel van 4096/4096 aangemaakt en dat ging binnen een halve minuut. Maar ik geloof dat dat vroeger zo een kwartier of langer kon duren.

Anoniem 22:23

Zelf vind ik deze wel handig omdat er op deze site minstens één Anoniem is die claimt dat een https servercertificaat nodig is voor de versleuteling van de verbinding en niet voor authenticatie van de server.

Overigens is het risico beperkt van een server die allerlei brakke cipher suites ondersteunt, want geen zichzelf respecterende en actuele browser gaat daar in mee.

Zelf ken ik dat boek niet, maar de auteur, Ivan Ristic {1} is de drijvende kracht achter ssllabs.com; zonder twijfel weet hij waar hij het over heeft.

{1} Op de laatste letter, 'c', moet je een schuin streepje denken (van linksonder naar rechtsboven); de Unicode letter daarvoor mag ik niet gebruiken op security.nl.

Strikt genomen heb je gelijk, maar dit is zinloze informatie die ronduit misleidend is voor mensen die dit niet precies snappen.

Net zo idioot is zeggen dat 110 dB maar 10 dB meer is dan 100 dB of, als het om een ongeluk en remweg gaat, 120 km/u maar 20% harder is dan 100 km/u. Vergelijkbaar verwarrend vind ik inflatiepercentages omdat niemand rekent met inkomstensstijgingspercentages (in de afgelopen 12 maanden).

Belangrijker: in https://gnupg.org/faq/gnupg-faq.html staat 2x onzin in het tweede deel hieronder:
Naast dat dit helemaal niet "marginal" is, klopt die 140 bits niet (volgens NIST - waar die FAQ zelf naar verwijst).

Op pagina 38 in de PDF die je hier (https://csrc.nist.gov/pubs/sp/800/56/b/r2/final) kunt downloaden staat "Table 2":

Geen rekening houdend met quantum computers en andere (momenteel nog) science fiction is de vergelijkbare sterkte van een 4096 bit RSA sleutel dus 152 (in plaats van 140) bits.

Dat is dus 40 extra bits, oftewel 2^40 = 1.099.511.627.776 maal zoveel mogelijkheden.

Als het, met een fictieve computer, 1 seconde zou duren om een 2048 bits RSA sleutel te kraken, en de "moeilijkheid" lineair is, duurt het kraken van een 4096 bits RSA sleutel meer dan 34.841 jaar (rekenend met 365,25 dagen per jaar wat niet helemaal correct is, en zonder rekening te houden met mogelijk ingelaste schrikkelsecondes).

Eerlijkheidshalve moet ik hierbij vermelden dat die 34.841 jaar wel eens aanzienlijk korter kan worden omdat er in dat tijdsbestek mogelijk veel snellere (quantum) computers worden ontwikkeld - anderzijds ging ik uit van 1 seconde voor een 2048 bits RSA sleutel, en als dat nú al zou kunnen, zouden we een gigantisch probleem hebben.

3 decibel is een verdubbeling (of halvering) herinner ik mij.
Energie neemt kwadratisch toe met de snelheid van een massa.


Wat ik fascinerend vind is de tabel in Appendix D en de formule die daarin staat. Is deze formule echt? Of is het een benadering van de gewenste curve door de NSA?

Maar Robert J. Hansen heeft een punt; Waarom hele grote RSA sleutels gebruiken als er ook EC is? Vooral als ondersteuning voor grote RSA sleutels opnieuw gecodeerd moet worden.

Waarom gebruikt de Amerikaanse overheid trouwens Let's Encrypt certificaten? Is Mozilla beter als iets waar ze zelf mee komen? Komt op mij niet echt geloofwaardig over ;-)

Anoniem 22:23

Degene op wie je antwoordde had het over verschil in cryptografische sterkte, niet over het verschil in het aantal bits.

Zoals jij redeneert is een 3-cijferig decimaal getal maar 50% "sterker" dan een 2-cijferig getal. Alleen neemt het aantal verschillende waarden dat je ermee kan weergeven niet met 50% toe maar met een factor 10, want 00-99 zijn 100 waarden en 000-999 zijn er 1000.

Als je met brute force een sleutel probeert te kraken gaat het om het aantal waarden dat je in het aantal bits kwijt kan. Dan maakt elke bit die je toevoegt de zoektocht twee keer zo lang; 28 bits toevoegen maakt de zoektocht ruim 268 miljoen keer zo lang; 40 bits maakt hem ruim 1099 miljard keer zo lang, zoals Erik aangaf. Dat scheelt heel wat meer dan de 25% die jij meende te zien.

Hou toch eens op met dat gezeur over de NSA overal.

Waarschijnlijk zal die formule asymptotisch wel min of meer kloppen - maar met heel dikke slagen om de arm.
Feitelijk is de 'equivalente sterke' vraag meer iets voor een management summary ;
Vliegtuigbouwers denken ook niet 'gewicht uitgedrukt in aantal olifanten' , en stadsplanners niet in 'oppervlakte in voetbalvelden' .

Het brute-forcen van een symmetrische key is op sommige manier makkelijk en prettig schaalbaar .
meer tijd, of meer chips/asics en je kunt een ietwat langere key testen . De resources per werker nemen alleen niet toe.
Je kunt tijd en het aantal parallele werkers heel goed uitruilen.

Het ontbinden van een RSA key heeft twee stappen :

Het 'zeven' - het vinden/genereren van heel veel relaties .
Deze stap is redelijk te paralleliseren .
Alleen - voor een grotere key heeft iedere individuele werker ook meer geheugen nodig.

Als je voor een 768 bit key bijvoorbeeld werkers met 64M geheugen nodig hebt, kun je die tijd om die key te ontbinden behoorlijk schalen door meer (of minder) werkers te gebruiken - met (bv) 64M geheugen .

Maar voor 2048 bit key heb je werkers nodig met erg veel meer (adresseerbaar) ram . Dan wordt tijd verkorten door meer werkers te gebruiken heel wat lastigers, want systemen met zoveel resources zijn niet makkelijk bij elkaar te krijgen.

Tenslotte vormen alle gevonden relaties een matrix die als stelsel van vergelijkingen opgelost moet worden.
Deze stap is minder goed paralleliseerbaar - en vergt ook veel geheugen .

Ik kan zo niet zeggen waar die formule uit de NIST appendix vandaan komt.

Maar ik speculeer dat het een vertaling zal zijn van de complexiteit van de GNFS (general number field sieve) ; Het algorithme dat het 'zeven' van relaties doet .

https://en.wikipedia.org/wiki/General_number_field_sieve

(na wat zoeken : https://www.osti.gov/servlets/purl/1647525 . Hoog over lijkt het inderdaad de omgeschreven tijd-complexiteit van de GNFS te zijn, en vertaald naar bits (ln2) .

Ik betwijfel een beetje of de toenemende geheugen eisen aan de GNFS werkers erin zit.

Voor een zwaar op de maag liggend - maar wel in depth - verhaal over de complexiteit (in tijd en in RAM) van NFS , zie bv
https://cr.yp.to/factorization/batchnfs-20141109.pdf

Je bedoelt:

Weet je hoe lang brute forcen op deze manier duurt?

Anoniem 22:23

Als we denken in geld/salaris - van 80.000 (5 cijfers) naar 80.000.000 (8 cijfers) . 3 cijfers erbij . 60% erbij _in aantal cijfers_ .

Maar 1000x zoveel in 'waarde' .

3DES zou een sterkte van 112 bits hebben, dus de 112 bits voor 2048 bits RSA "kwam wel erg goed uit".

Er zit een gevoelsmatig onverwachte niet-lineariteit in de tabel die ik eerder toonde, waarin E ontbreekt. Als ik die toevoeg en steeds de verschillen laat zien, krijg je deze tabel:


Het lijkt er dus op dat de sterkte van een RSA sleutel steeds minder toeneemt naarmate je het aantal mogelijkheden blijft verdubbelen (1 bit langer maakt). De E-kolom geeft daarbij een minder vertekend beeld dan de "estimated strength" kolom, waarin wel extreem is "afgerond" door NIST.

Maar sowieso geldt de gebruikte formule niet zodra er voldoende krachtige quantum computers bestaan en het Shor-algoritme uitvoerbaar blijkt. Het blijft m.i. natte vingerwerk "om een ruwe indicatie te geven".

Als je bewezen primes (niet her-) gebruikt is RSA ijzersterk gebleken. Niet elke EC-curve is echter veilig [1], en het risico op implementatiefouten is, naar verluidt [2], groter.

[1] https://safecurves.cr.yp.to/

[2] bijv. uit https://avinetworks.com/glossary/elliptic-curve-cryptography/:

Ik heb een bloedhekel aan DV-certificaten, omdat extreem veel exemplaren daarvan worden gebruikt voor phishing- en andere nepwebsites. De USA overheid heeft echter wel een (redelijk?) excuus: hun domeinnamen eindigen op .gov.

Als je bedoelt "totdat dit programma output geeft", dan: zeer kort (los van die eerste output, is dit programma verre van optimaal; bijv. STEP 2 toevoegen maakt het 2x zo snel).

Uberhaupt hoeft een trial division maar tot sqrt(N) te lopen.
Dit "programma" test dus 4094 bit keys .

Stoppen bij het eerste antwoord zou ook schelen .
En inderdaad is , na testen op 'even' alleen oneven getallen proberen de eerste erg voor de hand liggende optimalisatie .

maar goed - hopelijk weet 'iedereen' dat factoriseren weliswaar "moeilijk" is, maar in elk geval wel stukken sneller kan dan trial division, voor getallen van enige omvang.

Gigantisch, maar aan het antwoord (1) heb je niets.

Ah ja ;-)
Loop had natuurlijk bij 3 moeten beginnen, step 2, en een eerste test buiten de loop op even.
Oh well .

fwiw, bij priem _testen_ (random getal testen voor priem , om te gebruiken als deel van een secret key) is een eerste filter met trial division (op basis van array met de eerste X priemgetallen die je gebruikt als delers) wel efficient, voordat de wat complexere priem-testen gedaan worden.

Anoniem wilde een brute force doen van een 2048 bit RSA sleutel. Dat heb ik geprogrammeerd. Had eigenlijk ook met 0 willen testen maar dan krijg je een Division by zero. Dat veroorzaakt een hardware interrupt en stopt het programma.

Om zeker te weten dat je geen prime factor mist, zul je ze allemaal moeten testen. Ik bedoel, misschien is 2 wel een prime factor. Die mis je als je alle even getallen overslaat met STEP 2.

Anoniem 22:23

Ik vermoed dat dit met de dichtheid van priemgetallen te maken heeft: https://pyth.eu/dichtheid-van-priemgetallen. Als ik dit zo lees neemt het aantal priemgetallen niet lineair toe als je de getallenreeks laat toenemen. Ofwel er zitten in verhouding meer priemgetallen in 2^2048 dan in 2^4096. Daarmee zou het aantal public/private key pair in verhouding minder toenemen met de sleutellengte (2048 vs 4096)
Q

Ik denkt niet dat dat juist is.

Ik heb de linken naar de time-complexity van de GNFS gepost (16-9 22:03 ) , waar die formule uit het NIST paper op gebaseerd lijkt te zijn.

Ik kan me niet herinneren (maar ok - dat is wel voorbij de rand van mijn wiskunde kennis) dat de afleiding/heuristiek van die GNSF complexiteit heel direct relateert aan de priemdichtheid.

In elk geval is de GNFS complexiteit een andere orde dan x/log(x) , wat de asymptotische priem-dichtheid is.

Die complexiteit van de GNFS is zelfs nog steeds niet rigoureus bewezen. Ongoing research.

http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring


Zie ook https://crypto.stackexchange.com/questions/40533/o1-in-time-complexity-of-number-field-sieve

Die ook kijken naar de formule uit het NIST paper en de O(1) constante en hoe die praktisch in te vullen voor de vraag hoe moeilijk het ontbinden van RSA-1024 nou echt is .

Dank! Mijn (sowieso kleine) wiskundeknobbel zegt "zou kunnen". Wat wellicht ook "zou kunnen" is dat, naarmate de factoren langer worden, het steeds lastiger (tijdrovender) wordt om te bewijzen dat zij priemgetallen zijn.

In Table A.1 (pagina 34) uit de PDF die je uit https://csrc.nist.gov/pubs/fips/186-5/final kunt downloaden, vind je eisen t.a.v. lengtes van o.a. p en q voor Provable- en voor Probable primes.

Natuurlijk. Maar dat heeft helemaal niets te maken met het ontbinden in factoren .

Bewijzen (of extreem grote kans hebben) dat een getal priem is , is relatief makkelijk. Het wordt natuurlijk wel moeilijker met toenemende lengte .
Het genereren van een lange priemgetallen is alleen relevant bij het maken van nieuwe keys.

heeft iemand die presentatie wel bekeken ?

Ik heb er wat doorheen gezapt .
En ik zag niks dat een uur van mijn tijd waard was.

Vuistregel 1 - echte doorbraken in de wiskunde vind je niet (alleen maar) op youtube video presentaties, dan vind je eerst een publicatie in een serieus journal.