Niet heel direct denk ik - PGP gebruik is uberhaupt minimaal.

Gebruik je wel PGP - en ben je ook nog voldoende paranoide om te denken dat wat je schrijft echt geheim moet blijven, dan zou je het advies van de IBM link moeten volgen om eventuele ElGamal keys die je hebt te revoken, en te vervangen door RSA of ECC keys .

Die worden toch al weinig gebruikt - IBM vond een paar duizend ElGamal keys in de twee miljoen die ze bekeken op de keyservers.

Verder : als je interessant bent - maar leek - dan moet je niet je eigen dingen doen en anonieme adviezen van een forum gaan zitten volgen. Praat met de IT security officer van je werk of instelling, en gebruik niet je eigen spullen.

Ook ik ben een leek als om de wiskundige zaken gaan, en ik heb al eens op de zwakte van de wachtwoorden van deze PGP implementatie in Thunderbird gewezen, en ik zie dat één van mijn Thunderbird sleutels het kenmerk ElGamal heeft.
Dit is nog een sleutelpaar uit 2000, die met een standalone PGP programma is gegenereerd. Kenmerk DSA, en ElGamal.
Een huidige sleutelpaar gegenereerd in Thunderbird Openpgp heeft twee mogelijkheden, RSA en EC (Eclliptische Curve).
In beide sleutels ontbreekt het ElGamal protocol, dus zijn veilig. Versie Thunderbird (78.13.0 (64-bits))

Wat ik begrijp is dat het gebruik van ElGamal wordt afgeraden. Mocht je nog een PGP sleutel gebaseerd op ElGamal hebben: intrekken en vervangen door een moderne sleutel. Houd er rekening mee dat berichten die met ElGamal versleuteld zijn mogelijk gedecodeerd kunnen worden.
P.S. Het is geen slecht idee om iedere vijf jaar eens te kijken of je PGP sleutels nog wel sterk genoeg zijn.

De hele oude PGP RSA sleutels van de commandline versies van PGP 2.6.x gebruikten MD5 voor signing.
Daarna (met PGP 5.x) kwamen de PGP DH/DSS sleutels. Het signing gedeelte daarvan was gelimiteerd tot 1024 bits vanwege een Amerikaanse standaard voor DSS sleutels. Ook gebruikte deze versie SHA-1 voor signing.

MD5 en SHA-1 zijn gebroken en moeten niet meer gebruikt worden. Dus als je zulke oude keys nog hebt; nieuwe sleutels aanmaken en de oude revoken (nadat je een backup maakt). Deze sleutels kan je nog nodig hebben voor decryptie van je oude gegevens.

De paper van IBM gaat over de cryptografische library van GnuPG, Libgcrypt. Tot versie 1.8.8 en 1.9.3. Daar is de fout in gevonden. De laatste versie van GPG is al gepatcht en de meeste andere pakketten die er gebruik van maken zullen spoedig volgen.

In November 15-19, 2021 zal de paper publiek worden. Tot die tijd moet je alles patchen als er patches zijn.

Ik weet niet of Thunderbird de library Libgcrypt gebruikt. Ze hebben eigenwijs gekozen voor iets anders als GnuPG. Ook is het misschien niet zo handig in het algemeen om een tool te installeren om te kijken of je sleutels nog veilig zijn. Die tool zou theoretisch uit kunnen zijn op je DH sleutels.

P.S. DH en ElGamal zijn hetzelfde volgens mij. Semantiek.

Bedankt voor jullie antwoorden! Ik begrijp nu dat EIGamal protocol een bepaalde (wiskundige) mogelijkheid is om een sterk sleutelpaar te generen is.
Ben dan nu al een stap verder,.
Nogmaals bedankt voor jullie uitleg en hulp!

Gebruik blowfish van Bruce Schneier met keysize > 4096

De meest recente versie van Thunderbird gebruikt Libgcrypt-20.dll versie 1.8.5.22112.
In de map van Thunderbird, is Libgcrypt-20.dll versie 1.8.5.22112 te vinden, en dat is in de meest recente versie van Thunderbird. (78.13.0 (64-bits)) Dat zou betekenen dat de fout nog niet is gerepareerd, maar in de structuur eigenschappen van een in Thunderbird aangemaakt sleutelpaar staat alleen RSA vermeld.

Zoals ik al schreef bij het updaten van Thunderbird 91, de nieuwste versie is:

Thunderbird Release Notes

Version 91.0.3, first offered to channel users on August 26, 2021

In de Mozilla map Thunderbird 91.0.3, zie ik geen "Libgcrypt-20.dll" bestand staan, wel "libGLESv2.dll, libEGL,dll, libotr.dll"
Ik neem dus aan dat het voorgenoemde probleem, gepatcht is, of nu niet meer relevant is,.tot weer eens een nieuwe zwakke plek gevonden wordt,.

Bij OpenPGP sleutel aanmaken staat bij
Geavanceerde instellingen:
Keuze uit sleuteltype:
optie 1: RSA, Sleutelgrootte 3072 en 4096
optie 2: ECC (Elliptische Curve)
Ik neem aan dat RSA + 4096 een sterkere sleutel geeft dan 3072, maar er is meer rekenkracht nodig.

@Anoniem gisteren 19:18: ook de Crypto++ library had een kwetsbaarheid. En hoewel je MD5 en SHA1 voor de meeste cryptografische doeleinden niet meer moet gebruiken, hebben hun kwetsbaarheden niets te maken met het probleem wat de TS aankaart. Ik probeer hieronder te verduidelijken wat er (als ik het goed begrijp) aan de hand is.

Ja en nee ;-)
Uit https://www.research.ibm.com/blog/insecurity-elgamal-openpgp:

Mede uit de feitelijke onderzoeksresultaten (zie [1] en [2]) begrijp ik dat de onderzoekers -gelukkig- geen kwetsbaarheid in het "ElGamal encryption" protocol hebben gevonden. Risico's kunnen echter ontstaan door een mismatch tussen de software gebruikt door Bob (om een asymmetrisch sleutelpaar te genereren) en de software gebruikt door Alice (om een bericht te versleutelen met de public key van Bob).

[1] https://ibm.github.io/system-security-research-updates/2021/07/20/insecurity-elgamal-pt1
[2] https://eprint.iacr.org/2021/923

Om iets preciezer te zijn (als ik het goed begrijp), het risico onstaat door de keuze (door softwaremakers) van:
1) parameters gebruikt voor het genereren van het asymmetrische sleutelpaar van Bob;
in combinatie met
2) een "ephemeral" (bedoeld voor kortstondig gebruik, hier eenmalig) random getal, gekozen door de software van Alice, waamee Alice een bericht voor Bob versleutelt (gebruikmakend van de public key van Bob, gegenereerd met parameters gekozen door Bob's software).

In [1] vind je een cross-reference tabel met risico's die kunnen ontstaan tussen implementaties (libraries) van verschillende softwaremakers. Met de laatse versies zouden de problemen verholpen moeten zijn, maar met oudere versies gegenereerde sleutelparen en eerder daarmee versleutelde bestanden zouden kraakbaar kunnen zijn.

@Geïnteresseerde lezers: voor een beter begrip licht ik in de volgende bijdrage toe hoe (ik denk dat) ElGamal encryptie werkt (dat moet te volgen zijn als je weet wat machtsverheffen is, "moeilijker" wiskunde probeer ik te vermijden of licht ik toe).

Uit die toelichting hieronder blijkt dat er sprake is van ten minste 5 parameters voor het genereren van een sleutelpaar en versleutelen van één bestand. De gepubliceerde kwetsbaarheden lijken vooral betrekking te hebben op (achteraf) onverstandige keuzes van combinaties van die parameters, vooral omdat hier verschillende softwaremakers bij betrokken kunnen zijn.

Wellicht vaker, en "sterk genoeg" kun je, zoals blijkt, niet altijd afleiden uit de (bit-) lengte van de sleutel(s). Je zult de media en/of nieuws van de softwaremakers moeten volgen om te weten of jouw sleutels nog bruikbaar zijn en of je wellicht oudere sleutels moet intrekken (revoken).

Uitleg van de werking van ElGamal encryptie, althans voor zover ik de werking begrijp (ik vind de materie interessant maar ben geen cryptograaf). Ik hoop dat ik geen domme dingen schrijf, correcties en aanvullingen zijn van harte welkom! Lezers worden verzocht te checken of ik hieronder latere bijdragen met aanvullingen/correcties heb toegevoegd (want ca. 1 uur na het posten van een bijdrage kan ik er niets meer in wijzigen).

Vooraf, voor TS en andere lezers: het doel van asymetrische encryptie is dat jij, indien jij een public key van Bob hebt (en zeker weet dat deze van de jou bekende Bob is), en alleen Bob de bijpassende private key heeft, jij een bericht voor Bob met Bob's public key kunt versleutelen, waarna niemand anders dan Bob dat versleutelde bericht kan ontsleutelen (nl. met Bob's private key). Tenzij die versleuteling kwetsbaarheden kent natuurlijk, waaronder die in specifieke situaties kunnen optreden xoals beschreven door Luca De Feo, Bertram Poettering, Alessandro Sorniotti in [1] en [2] (zie mijn vorige bijdrage).

ElGamal encryptie
Zoals gezegd, ik ben geen cryptograaf, maar de uitleg van ElGamal encryptie in [3] kon ik goed volgen - waarbij de rekenvoorbeelden met kleine getallen (in de praktijk onbruikbaar, want simpel te kraken) in de cyaankleurige vlakken kunnen helpen begrijpen hoe e.e.a. in z'n werk gaat.

[3] https://www.di-mgt.com.au/public-key-crypto-discrete-logs-3-elgamal.html (de eerste beschrijving die ik, na zoeken op internet, goed kon volgen)

Domain parameters
Wat je moet weten is dat ElGamal encryptie van dezelfde "domain parameters" gebruik maakt als het Diffie-Hellman key agreement protocol (laatstgenoemd protocol wordt tegenwoordig bij het opzetten van nagenoeg elke https verbinding gebruikt). Die "domain parameters" bestaan uit drie getallen: twee priemgetallen p en q alsmede een ander getal g. In [4] kun je lezen hoe die getallen worden gegenereerd, en na genereren op geldigheid kunnen worden gecheckt (alles eveneens voorzien van voorbeelden met onrealistisch kleine getallen).

[4] https://www.di-mgt.com.au/public-key-crypto-discrete-logs-1-diffie-hellman.html

Berekenen ElGamal sleutelpaar voor Bob
Vereenvoudigd: gegeven p, q en g kan Bob's software een sleutelpaar genereren door een random getal b te kiezen, de private key. De "bijpassende" public key B wordt dan berekend (door Bob's software) als volgt:

Hierbij staat "mod" voor de modulus functie, oftewel de rest na deling met gehele getallen (7 mod 4 = 3, want 7 / 4 = 1, rest 3). Je ziet q niet terug in deze formule; deze is echter wel nodig, omdat de gekozen random private key b kleiner moet zijn dan q - 2 (zie [5]).

[5] https://www.di-mgt.com.au/public-key-crypto-discrete-logs-1-diffie-hellman.html#note2q2

De in [4] gebruikte kleine getallen p=283, q=47, g=60, alsmede (uit [3]) Bob's private key b=7, maken hoofdrekenen (voor de meesten 8-) lastig, want je komt bijv. 60^7 tegen. Daarom gebruik ik als voorbeeld hier nog kleinere getallen (hartstikke kraakbaar in de praktijk). Uitgaande van p=11, q=5, g=9 en Bob's private key b=2 wordt de formule:

Bob verspreidt zijn public key
Als Bob wil dat Alice een bericht bestemd voor Bob versleutelt voor verzending, moet hij zijn public key B samen met de drie domain parameters p, q en g naar Alice sturen. Gemakshalve noemen we die feitelijke public key B plus de domain parameters de public key van Bob, die hij ook op een publieke keyserver kan zetten.

Van het grootste belang is dat niemand uit die gegevens de feitelijke private key b van Bob kan uitrekenen. Daarom is het onder meer noodzakelijk dat p een zeer groot priemgetal is, bij voorkeur een safe prime. Een safe prime p is een priemgetal waarvoor geldt dat q ook een priemgetal is in p = 2 * q + 1. In de begintijd van PGP waren computers niet krachtig genoeg om (voor grote p) vast te stellen of p een safe prime was. Daardoor kan een voldoende grote sleutel (bijv. 2048 bits) toch zwak zijn. Ook moeten q en b niet te klein zijn en ook aan g worden eisen gesteld.

Alice versleutelt bericht voor Bob
Als Alice een bericht m versleuteld naar Bob wil sturen, genereert haar software een ephemeral random getal k kleiner dan q - 2. Vervolgens berekent haar software:

Stel dat het te versleutelen bericht m gelijk is aan 6 en de software van Alice voor k de waarde 3 gekozen heeft:

Alice stuurt versleutelde bericht naar Bob
Het versleutelde bericht bestaat uit de twee componenten c1 en c2. Vertaald uit [3], cryptograaf Neal Koblitz zou dit paar beschreven hebben als volgt: c2 is het bericht m "met een masker" en c1 is een "hint" die kan worden gebruikt om het masker te verwijderen, maar alleen door iemand die de private key b kent.

Decryptie door Bob
Bob ontvangt c1 en c2 en berekent:

Met de kleine voorbeeldgetallen:

Asymmetrische encryptie van grote berichten
Ik heb hierboven enkele details weggelaten: o.a. de rol van g, maar ook dat m niet groter mag zijn dan p - 1 (bij een bitlengte van p van 2048 hits kan dit flink minder zijn dan 256 bytes). Omdat je meestal grotere bestanden wilt versleutelen, wordt tevens gebruik gemaakt van symmetrische encryptie, vaak AES. Er wordt dan door Alice een random symmetrische sleutel m gegenereerd waarmee het hele bericht wordt versleuteld, waarna die symmetrische sleutel m als "bericht" wordt gebruikt in de hierboven beschreven ElGamal versleuteling. Alice stuurt dan, naast c1 en c2, ook het symmetrisch versleutelde bericht naar Bob. Zodra Bob m (nu de symmetrische sleutel) heeft berekend uit c1 en c2, kan hij het meegezonden symmetrisch versleutelde bestand ontsleutelen met m.

Nee, ElGamal is net niet hetzelfde als Diffie-Hellman .

Meneer El Gamal heeft echt iets bijgedragen en niet zomaar z'n naam over het werk van de heren DIffie en Hellman geplakt.
Diffie-Hellman key exchange werkt alleen online - prima dus bij HTTPS, SSH e.d.

Maar niet voor iets als PGP . Taher El Gamal heeft een variatie bedacht - op dezelfde wiskundige basis van discrete logarithmen als waarop DH gebaseerd is , maar wat wel werkt voor offline gebruik zoals bij PGP .
Dus wel erg verwant - maar niet terecht om te zeggen 'alleen een semantisch verschil' .

Er zijn - zowel voor RSA als voor ElGamal - in een naïeve implementatie diverse risico's waarbij een aanvaller dingen kan leren over gebruikte sleutels.
Dat slaat niet op 'technische' bugs (zoals het exploiten van bufferoverflows, of side channels) , maar gebaseerd op de wiskunde van een recht-toe-recht-aan implementatie van RSA dan wel ElGamal .

Ik speculeer dat IBM zo iets gevonden heeft in GPG.

Voor een paper met voorbeelden (pittige kost) van dergelijke risico's van een tekstboek-implementatie , zie
https://link.springer.com/content/pdf/10.1007/3-540-44448-3_3.pdf

In de context van PGP/GPG zijn ze identiek. Zie https://gnupg.org/faq/gnupg-faq.html#compatible:


Ik vind het erg ongelukkig om een asymmetrisch encryptie algoritme, halverwege het bestaan van een programma totaal en onherkenbaar te hernoemen. NAI heeft een fout gemaakt met PGP 5, en GnuPG heeft dit recht gezet. Waardoor het nu lijkt dat er vier asymmetrische encryptie algoritmes zijn: RSA, Diffie-Hellman, Elgamal en Elliptic Curve.

Hoe het echt zit (uit de specificaties in RFC 4880):

Anoniem 19:18

Ah, thx. Ik wist niet dat de verwarring DH/ElGamal naamgeving zich ook/zelfs uitstrekte tot PGP devs.

In mijn laatste bijdrage hierboven (https://security.nl/posting/718236) leg ik uit hoe ElGamal encryptie werkt. Daarbij wordt van dezelfde "domain parameters" p, q en g gebruik gemaakt als bij Diffie-Hellman, maar daarna zijn er m.i. significante verschillen.

Bij DH genereren beide partijen een ephemeral sleutelpaar. Om preciezer te zijn, bij DH gebeurt het volgende, ervan uitgaande dat Bob de domain parameters genereert (je kunt Alice en Bob desgewenst verwisselen):

Bob:
- genereert de domain parameters p, q en g (zie mijn vorige bijdrage hoe);
- kiest een ephemeral random private key b waarvoor geldt 2 <= b <= q - 2;
- berekent bijpassende public key B = g^b mod p;
- stuurt naar Alice: B, p, q en g;

Alice:
- kiest een ephemeral random private key a waarvoor geldt 2 <= a <= q - 2;
- berekent bijpassende public key A = g^a mod p;
- stuurt naar Bob: A;
- berekent shared secret s = B^a mod p;

Bob:
- berekent shared secret s = A^b mod p.

Beide partijen kennen nu s zonder dat een passieve MitM s kan achterhalen (tenzij er zwakke parameterwaardes gebruikt zijn of de MitM over een voldoende krachtige en betrouwbare quantumcomputer beschikt). Nb. een actieve MitM kan zich richting Bob voordoen als Alice en vice versa, en zo de (verschillende) s'en eenvoudig achterhalen (vandaar dat bij https een https server certificaat gebruikt wordt voor de authenticatie van de server; bij de versleuteling van de verbinding speelt zo'n certificaat geen rol).

Merk op dat het shared secret s direct uit beide ephemeral sleutelparen wordt afgeleid. Bij ElGamal encryptie stuurt de versleutelende partij twee parameters terug naar de eigenaar van de public key. Hoewel je dat een "detail" zou kunnen noemen, vind ik dit toch echt wel iets anders. Daarnaast biedt ElGamal geen forward secrecy, terwijl dat nou juist het doel is van DH indien ingezet bij https verbindingen.

Als je ElGamal en DH als hetzelfde ziet, kun je alle "oude" asymmetrische crypto wel op één hoop gooien. RSA werkt immers met vergelijkbare wiskunde: c(m) = m^e mod n
(bron: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Encryption).

Ik kom van PGP 2.6.3i en daarna PGP 5.5.3i en voor gebruikers als mij is het:
1) RSA version 3 public key
2) DH version version 4 public key
3) RSA version 4 public key
4) EC public key

Toen PGP 5.0 uitkwam was er nog een patent op RSA. En niet op DH. Daarom is toen voor DH gekozen. Toen in het jaar 2000 het patent op RSA verliep, is men bij PGP/GPG weer RSA sleutels gaan genereren. Maar dan version 4 in plaats van version 3.

Ook vanwege een patent op het encryptie algoritme IDEA, wat exclusief gebruikt werd in PGP 2.x, is IDEA later standaard uit GnuPG gehaald en later weer toegevoegd. Ik weet niet of het er nu nog inzit maar in GnuPG 1.4.23 zit het nog wel. Het is de enige manier om oude data met version 3 public keys nog te decrypten. Tenzij je nog een 16/32 bit computer hebt staan die met PGP 2.6.3i om kan gaan.

Anoniem 19:18

Dank voor alle bijdragen. Dit is een verdiepingsslag, hardcore security.

In het voorbeeld van Erik van Straten van 29-08-2021 15:03 is de message "m", en in het voorbeeld m=6.
Deze "m" kan ook de random symmetrische sleutel "m" zijn van een groter bestand. Dat snap ik.

Ik begrijp het nu zo, dat vervolgens ieder afzonderlijk ASCII teken (of bij een grafisch bestand de pixelwaarde?) in dat grotere bestand moet worden versleuteld (vermenigvuldigd) met deze random symmetrische sleutel "m"? En bij decrypten het omgekeerde plaats vindt, dus delen door de symmetrische sleutel?

En klopt het dat een computer technisch gesproken minder makkelijk delingen uitvoert dan vermenigvuldigingen, helemaal als gedeeld moet worden door grote priemgetallen? Zodat van deze "zwakte" gebruik kan worden gemaakt om decrypten te bemoeilijken?

Fijn om te lezen dat mijn uitleg begrepen wordt!

Nee, dat is niet hoe moderne symmetrische encryptie werkt (we noemen dat type encryptie "symmetrisch" omdat dezelfde sleutel voor versleutelen als voor ontsleutelen wordt gebruikt).

Effectief bestaat elk bestand uit een reeks bits. Voor het gemak werken we meestal met groepjes van 8 bits die we een byte noemen. Met 8 bits kan een byte 256 verschillende bitcombinaties bevatten. Wat een bitcombinatie betekent is volledig afhankelijk van de toepassing. Een byte kan bijv. binair 01000001 (links het meest significante bit) bevatten, dat we (normaal gesproken) decimaal 65 noemen. Als die byte een ASCII letter representeert, is dat de hoofdletter 'A'. Maar het kan ook de grijswaarde zijn van één pixel in een plaatje met 256 grijswaarden per pixel, of een van 4 bytes zijn die een 32-bit geheel getal voorstellen, of een (onderdeel van een multi-byte) CPU-instructie zijn. De mogelijkheden zijn eindeloos.

Voor digitale versleuteling maakt het niet uit waar de bitcombinaties in bytes voor worden gebruikt. Daardoor kun je elk digitaal bestand versleutelen.

De basis voor symmetrische encryptie is meestal de XOR (eXclusive OR) operatie. Deze werkt per bit:

Met andere woorden, het outputbit wordt 1 als ofwel het Inputbit ofwel het Sleutelbit 1 is (vandaar exclusive or). In https://www.security.nl/posting/468370/Encryptie+voor+leken+-+en+waarom+verzwakken+onverstandig%2C+en+verbieden+zinloos+is heb ik XOR vergeleken met de elektrische "hotelschakeling", bekend van de lichtknopjes onderaan en bovenaan een trap waarmee je zowel beneden als boven het licht aan en uit kunt doen. Een andere manier om ernaar te kijken is optellen zonder "onthouden".

In de huidige praktijk zal m vaak 128 of 256 bits lang zijn. Dat is ruim voldoende als je maar 1 byte wilt versleutelen. Als voorbeeld zou ik ik de laagste 8 bits van een sleutel m kunnen nemen. Stel dat dit toevallig 10100101 is:


Merk op dat de waarde van de sleutel niet uitmaakt voor dit proces. Het is zelfs totaal niet erg als een inputbit niet wijzigt tijdens de versleuteling, mits een aanvaller dit niet weet. M.a.w. voor een aanvaller moet de kans 50% zijn dat een bit, tijdens de versleuteling, is gewijzigd of niet.

Als je grotere bestanden dan bijv. 256 bits (32 bytes) wilt versleutelen, loop je bij symmetrische encryptie al snel tegen hetzelfde probleem aan als bij asymmetrische encryptie: je kunt de sleutel niet eindeloos lang maken. Daar hebben cryptografen twee verschillende oplossingen voor bedacht: block ciphers en stream ciphers.

Sterk vereenvoudigd worden, bij een block cipher, de inputbytes tevens als sleutel voor andere input bytes gebruikt in een specifieke volgorde, terwijl decryptie in de omgekeerde volgorde plaatsvindt. De lol van XOR is dat dit straffeloos mag! Bij block ciphers wordt vaak een IV = Initialisatie Vector gebruikt. Een enorm vereenvoudigde block cipher zou er uit kunnen zien als volgt:

Dit is overigens een waardeloze cipher omdat, bij ASCII input, het meest significante (meest linkse) bit van elke versleutelde byte altijd 1 is. Bij serieuze block ciphers worden bits ook onderling geswapped (o.a. door roteren of schuiven van bits in bytes of groepen van andere aantallen bits dan 8). Maar het gaat om het idee ;-)

Een sterk vereenvoudigde stream cipher zou gebruik kunnen maken van een cryptografische hashfunctie, als volgt:

Met stream ciphers wordt getracht een, als onkraakbaar bekend staand, "One Time Pad" (met random sleutel die net zo lang is als de input) te benaderen. Dat lukt niet erg goed; in de praktijk worden later vaak "biases" ontdekt in stream ciphers (zoals in RC4). D.w.z. als je een zeer groot bestand met bijv. alle bytes nul versleutelt, zou je niet van random te onderscheiden output moeten krijgen, maar in de praktijk blijkt vaak dat in de output sommige byte-waardes vaker voorkomen dan andere.

Delen is niet persé moeilijk. Stokoude elektronische rekenmachines hadden daar al verbazend weinig moeite mee (met, toegegeven, geen astronomisch grote getallen).

Ik hoop dat ik dit goed verwoord (verbeter me svp als ik dit niet goed heb of het duidelijker kan): de essentie bij klassieke asymmetrische versleuteling is dat het, voor de nu bekende computers, extreem tijdrovend is om het resultaat van twee met elkaar vermenigvuldigde, zeer grote, priemgetallen te ontbinden in (de twee) factoren en/of het voor die computers enorm tijdrovend is om uit de formule x^y mod p, waarbij x bekend is, te achterhalen wat random y en priemgetal p zijn.

Erik legt heel grondig uit - maar ik denk dat je wat stappen niet snapt .

In elke implementatie wordt het feitelijke bestand versleuteld met AES (of 3DES, of Blowfish of ..).
Er wordt een willekeurige sleutel gegenereerd voor die AES encryptie - die sleutel is 128 (of 192,of 256) bytes groot.

Het is alleen die *sleutel* die met ElGamal, of RSA, ge-encrypt wordt.

Waarom : omdat alleen ElGamal/DH, of RSA - 1) baggertraag zijn, en 2) behoorlijk onveilig als je de input data niet goed controleert .
(daarom wordt er nog 'padding' - een set extra bytes, mee ge-encrypt).

Maar of het nu een sleutel, of wat anders is : De public-key encryptie neemt zo'n boodschap, beschouwt die als een reeks bitten, en doet daar het modulaire machtverheffen op.

En decryptie doe je ook door modulair machtsverheffen - alleen met de geheime sleutel .

Dat is dit stukje uit Erik's uitleg :


De decryptie is dus : A^b mod p.

Bij RSA is het ietwat simpeler uit te leggen :

M' = M^e mod n is encryptie , M'^d mod n is de decryptie .

En eigenlijk moet je nu heel lang gaan zitten lezen over modulair rekenen .
Want dat is FORS ANDERS dan gewoon de machtverhef-knop op je rekenmachine.


Het klopt dat delen echt moeilijker is dan vermenigvuldigen . Voor zo ver ik weet is dat geen onderliggende oorzaak van waarom public key encryptie werkt en het kraken ervan -vermoedelijk - moeilijk is.

Waar staan we qua DH/Elgamal en RSA :

"We" - dat wil zeggen alle publieke wiskunde - denken dat

1) de beste manier om DH/Elgamal te kraken het oplossen van het discrete logarithme is . En dat de beste manier om RSA te kraken het ontbinden in factoren is van de sleutel 'n' .

We hebben alleen geen bewijs _dat_ factorisen / discrete log de optimale manieren zijn om boodschappen te lezen , of dus dat het kraken van RSA/DH minimaal zo moeilijk is als factoriseren/discrete log oplossen.

2) We hebben ook geen bewijs dat factoriseren/discrete log fundamenteel moeilijk zijn.

Fundamenteel moeilijk is (min of meer) bewijzen dat het best mogelijke algorithme een complexiteit waarbij het werk sneller dan polynomiaal toeneemt.
Bijvoorbeeld : gewoon vermenigvuldigen op de lagere school manier heeft een complexiteit van O(N^2) , met N het aantal cijfers dat je vermenigvuldigt . Dat is polynomiaal - N tot de een of andere vaste macht. Iets dat een complexiteit heeft van O(2^N) is 'Niet Polynomiaal' - hier exponentieel .
Dat zijn problemen die wel moeilijk zijn als de input groeit.

(google tips : "Big O notatie" en "P vs NP") .

De beste algorithmen die we nu kennen voor factorisatie en discrete log zijn super polynomiaal .
Of het beter kan - als algorithme - weet niemand.
Er zijn wel in de jaren tussen het uitvinden van public key encryptie en nu een serie betere algorithmen ontdekt.

Interessant - en reden voor veel hype - is dat deze problemen door een quantum computer efficient opgelost kunnen worden. Wat ook niemand weet is of een quantum computer echt gebouwd kan worden voor het formaat sleutels die gebruikt worden.
Op moment werkt het alleen voor speelgoed formaat problemen - 15 = 3x5 .

Zie ook mijn andere antwoord .
Ah. En dat was onjuist hieromtrent.

Deling _is_ qua implemtatie moeilijker dan vermenigvuldigen - (ook te zien aan het verschil in klokcycles tussen div en mul) .
maar asymptotisch wel dezelfde orde complexiteit als vermenigvuldigen.
- oeps , dat had ik eerst beter moeten controleren.

Dat is omdat heel grote delingen omgezet worden in vermenigvuldigen , en dan , afgezien van een bepaalde constante factor - dezelfde complexiteit hebben.

zie https://en.wikipedia.org/wiki/Division_algorithm

Delen is dus een factor moelijker dan vermenigvuldigen.

Dank voor de reacties! Dit type bijdragen maken Security.nl de moeite waard.
@Erik van Straten 01-09-2021 19:26:
Ik roep iets over een klepel en een klok. En jij schrijft zeer zorgvuldig en uitgebreid naar het antwoord: het ontbinden van een product van twee heel grote priemgetallen in de twee factoren is (zeer) tijdrovend. Encryptie en decryptie zijn lastige onderwerpen, ook de Wikipedia pagina's zijn niet makkelijk leesbaar. Jouw bijdrage vind ik wel dusdanig goed leesbaar, dat ik het inclusief de XOR omzettingen letterlijk (bit-voor-bit :-) snapte terwijl ik het gisteravond las op het kleine scherm van mijn smartphone.

@Anoniem van 01-09-2021 23:07
Delen is (iets) moeilijker dan vermenigvuldigen voor een CPU, ik denk dat dat nu (nog) het kraken van public key encryptie (een beetje) belemmert. Totdat de quantum computers worden ingezet. Dat zou het einde betekenen van dit type encryptie?
Ik ga jouw stuk goed bestuderen, gelukkig heb ik "klokrekenen" geleerd dus dat "x mod y" snap ik (in principe).
"Big O" op Wikipedia opgezocht inmiddels, ik ben in de ICT helaas nog niet verder gekomen dan "Big Endian" ;-)

Anoniem van 01-09-2021 14:33
(dit is mijn tweede reactie, het is druk hier met al die Anoniemen ;-)