Hoe krijgen we met RSA de verbinding veilig?

De Rabobank bijv. versleutelt het berichtenverkeer tussen jou en de bank. Aan de éne kant wordt geëncrypt en aan de andere kant wordt gedecrypt en andersom. Dat wordt gedaan met dezelfde sleutel (symmetrische cryptografie). Deze sleutel (een getal of een in cijfers omgezette tekst) moet aan beide kanten bekend zijn, maar voor derden een geheim. Daarvoor gebruikt de bank RSA.

Het gaat zo: De bank is in bezit van een public key (e,n) en een private key (d,n), die geheim is. Op jouw apparaat wordt min of meer at random een getal (g) gegenereerd. Met de public key wordt g geëncrypt: g^e mod n = c. Het versleutelde resultaat (c) gaat over de lijn naar de bank. De bank vervolgens maakt van de bijbehorende private key gebruik om g te berekenen: c^d mod n = g. Aan beide kanten bezitten ze nu de sleutel (g) om berichten te versleutelen resp. te ontsleutelen. De verbinding is nu veilig.

 

Een voorbeeld met n= 33, e=3, d=7 en g=2 (n wordt de modulus genoemd en mod staat voor modulo rekenen oftewel klok-rekenen of restbepaling).

 

   2³ mod 33 = 8 (omdat 8 = 0 * 33 + 8, zoals 14 uur 2 uur is, omdat 14=1*12 +2)

   8⁷ mod 33 = 2 (omdat 2.097.152= 63.550* 33 + 2)

 

Het eerste plaatje hieronder verbeeldt deze processen.

De getallen n en e zijn in principe publiek. Onderschept iemand c en wil hij g vinden dan moet dit probleem worden opgelost: x^e mod n = c.

Bij een n van 200 cijfers en een groot getal voor e ziet het vlak met punten in het tweede plaatje verderop er heel anders uit. Het is totale chaos en er zit niet anders op dan de getallen tussen 1 en n-1 uit te proberen.

 

Wat mij interesseert is: had ik dit allemaal zelf kunnen bedenken?

Het probleem dat voorligt is: vind de functies F en H, zodat F(g)=c en H(c)=g. Waaruit volgt: H(F(g))=g en g₁#g₂ è F(g₁)#F(g₂). F is publiek, want je moet weten hoe c te berekenen. Ondanks het bekend zijn van F moet g niet dan met grote moeite zijn af te leiden uit c (mocht dit getal onverhoopt van de lijn zijn afgetapt).

 

Kwadrateren is de inverse van worteltrekken. Hiervoor geldt inderdaad: H(F(g))=g. Staat F voor kwadrateren en c=16 dan weet je meteen dat g=4. Dus de functies voldoen toch niet.

Er wordt iets vooruit gezet en teruggedraaid of doorgedraaid en het aantal getallen is eindig. Zouden we dan niet aan de cijferplaat van een klok denken?

 

Laten we van F(g) maken: g^e mod n = c, met g als variabele. Per definitie is dit ook te schrijven als: g^e = k₁*n + c of c=g^e – k₁*n.  En laten we van H(c) maken: c^d mod n = g. Vullen we c hierin dan krijgen we: (g^e – k₁*n)^d mod n = g.

(g^e – k₁*n)^d mod n = (g^e*d – k₂ * n) mod n = g^e*d mod n – (k₂ * n) mod n = g^e*d mod n = g.

Het is nu de taak de  juiste combinatie van n, e , d te vinden. Merk op, dat de laatste formule voor alle g’s geldt.

 

Wat betreft n. Het getal wordt zomaar cadeau gedaan. Je zou n als product van twee priemgetallen kunnen aanbieden: n =p*q. Zo’n product is notoir moeilijk te ontleden. De opdracht is nu de juiste combinatie van d, e, p en q te vinden.

 

Wat betreft g. Is g één van de priemgetallen of een veelvoud daarvan dan komen we in de problemen. Stel g=k₁*p (met k₁= 1, 2 etc.). (k₁*p)^e mod p*q =c oftewel (k₁*p)^e = k₂*p*q + c.

Deel beide kanten door p: k₁^e*p^{e -1} = k₂*q + c/p. Voor c moet dan gelden dat c = p of een veelvoud van p. Dat is een inperking van mogelijkheden en je wilt nu juist zoveel mogelijk chaos. Dus we kiezen een g, die geen priemgetal laat zien bij ontleden (factoriseren).

 

We gaan terug naar formule g^e*d mod n = g è g^e*d = k₁*p*q + g. Links en rechts delen door g geeft: g^e*d-1 = k*p*q + 1 ofwel g^(e*d-1) mod p*q =1.

 

Wat betreft groep G. Het getal g ligt tussen 0 en p*q en g is p noch q noch een veelvoud daarvan. In ons voorbeeld: G={1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32}.

 

Stelling: Als g₁€G en g₂€G è (g₁*g₂) mod p*q € G.

Bewijs uit het ongerijmde: g₁*g₂ = k*p*q + c. Is c geen element van G dan is deze te herschrijven als bijv. c=ç*p.

è  (g₁*g₂₎/p = k*q + ç. Rechts van = staat opgeteld een geheel getal en links een breuk, want niet deelbaar door p. Dat kan niet, dus c€ G. Q.E.D.

 

Hoeveel elementen bevat deze gesloten multiplicatieve groep? Het is aantal is p*q -1 – (q-1) – (p-1)= p*q –q –p +1= (p-1)*(q-1). In ons voorbeeld met p=3 en q=11 is het aantal 20.

 

Stelling: g^{k*(p-1)*(q-1)}mod p*q=1 (dit deel heb ik niet zelf bedacht).

Eerst een tussenstelling: Als g, g₁, g₂ € G dan: g₁#g₂ èg*g₁ mod p*q # g*g₂ mod p*q.

Bewijs uit het ongerijmde: Stel g*g₁ mod p*q = g*g₂ mod p*q è g*g₁ – k₁*p*q = g*g₂ – k₂*p*q è g*(g₁ - g₂) = k₃*p*q è g*((g₁ - g₂)/(p*q)) = k₃è (g₁ - g₂) = k*p*q, want een breuk kan niet en g niet deelbaar door p*q.

Het verschil kan hoogstens q*p -1 -1 èk=0 en g₁ = g₂. Q.E.D.

Hier staat dat g*g₁ mod p*q bijv. g₅ oplevert en dat dus g*g₂ mod p*q dat niet zal doen.

 

Bewijs:

(g*g₁ * g*g₂ * g*g₃ * ……. g*g_(p-1)(q-1)) mod p*q =

( ( (g*g₁) mod p*q)   * ((g*g₂) mod p*q) *  ……. ((g*g_(p-1)(q-1)) mod p*q) ) mod p*q=

( g₅ * g₂ *….. g_(p-1)(q-1)* …….g₇) mod p*qè

(g*g₁ * g*g₂ * g*g₃ * ……. g*g_(p-1)(q-1)) – k₁*p*q=( g₅ * g₂ *….. g_(p-1)(q-1)* …….g₇) –k₂*p*q.

g^(p-1)*(q-1)*(g₁*g₂*g₃* ……. g_(p-1)(q-1)) – k₁*p*q=( g₅* g₂ *….. g_(p-1)(q-1)* …….g₇) –k₂*p*q.

(g^(p-1)*(q-1) – 1) *(g₁*g₂*g₃* ……. g_(p-1)(q-1))= k₃*p*q.

 

Dit klopt alleen als (g^(p-1)*(q-1) – 1)/p*q = k è g^(p-1)*(q-1)=k*p*q +1 oftewel: g^(p-1)*(q-1)mod p*q=1.

 

Je kunt dit (g*g₁ * g*g₂ * g*g₃ * ……. g*g_(p-1)(q-1)) k keer herhalen.

Uiteindelijk hebben we dus g^{k*(p-1)*(q-1)}mod p*q=1.

 

 

We hebben nu g^(e*d-1) mod p*q =1 en g^{k*(p-1)*(q-1)}mod p*q=1 è e*d-1= k*(p-1)*(q-1)è

e*d mod (p-1)*(q-1)=1.

De opdracht is nu gegeven een p en q de juiste e en d te vinden (hier is ook een algoritme voor).

Gaan we terug naar ons voorbeeld e*d mod 20= 1. Oplossingen zijn (3,7) en (9,9). Aan dat laatste heb je natuurlijk niets. (3,27) is geen oplossing, omdat g²⁷ mod 33 =(g²⁰ * g⁷) mod 33 = ((g²⁰mod 33) * (g⁷ mod 33)) mod 33= g⁷ mod 33. Er geldt immers g²⁰mod 33=1. Dus 27 wordt gewoon gereduceerd tot 7.

 

Voor e en d geldt, dat ze (dus) inliggen tussen 1 en (p-1)*(q-1) en dat ze geen andere deler gemeen hebben met (p-1)*(q-1) dan 1. Dat laatste is nog te bewijzen.

Ik laat eerst zien, waarom e geen deler kan zijn van (p-1)*(q-1).

 

  x           2^x           2^x mod33

 

  0               1              1

  1               2              2

  2               4              4

  3               8              8

  4             16            16

  5             32            32

  6             64            31

  7           128            29

  8           256            25

  9           512            17

10         1024              1

11

 

 

20                                1

 

Vanaf x=10 herhaalt zich het treintje:{1,2,4,8   …17}.

 

Je hebt de zekerheid dat g⁰ =1 en dat g^(p-1)*(q-1) mod p*q =1 (eerder bewezen). Tussen de beide uitersten past 1 trein of meerdere treintjes van getallen. In ons voorbeeld in principe: 1, 2,4,5,10. Concreet passen in ons geval twee treintjes. Maar het gezochte getal e kan dus nooit 10 zijn, want dan zou voor bijv. 4 moeten gelden: 4¹⁰ mod 33 = 2¹⁰*2¹⁰ mod 33=1.

Er zou dan voor bepaalde getallen gelden: g₁#g₂ è g₁^e mod (p*q) = g₂^e mod (p*q). En dat is iets wat we niet willen. De facto zullen 2 en 4 altijd deel uitmaken van G.

 

Een algemenere stelling: ggd (e, (p-1)*(q-1)=1.

Bewijs: Stel e en (p-1)*(q-1) hebben r als gemeenschappelijke deler (zoals bij 6 en 20 2 gemeenschappelijk is).

e*d = k*(p-1)*(q-1) + 1 è (e/r)*d = k* ((p-1)*(q-1))/r + 1/r.

Links staat een geheel getal en ((p-1)*(q-1))/r is een geheel getal en dus blijft een breuk over. Dus krijg je nooit een oplossing voor d. Q.E.D.

 

Voor de volledigheid controleren we nog: g₁#g₂ èg₁^e mod (p*q) #g₂^e mod (p*q).

 

Ditmaal geen bewijs uit het ongerijmde.

g₁^e mod (p*q)=c₁. Deze c₁ invullen in c₁^d mod (p*q) è

(g₁^e – k₁*p*q)^d mod (p*q)= g₁^e*d mod (p*q) = (g₁*g₁^{(e*d -1)}) mod (p*q) =

(g₁ mod (p*q))*(g₁^{(e*d -1)}) mod (p*q)) mod (p*q) = g₁ mod (p*q) = g₁.

 

Dus g₁ è c₁ en c₁ è g₁ en niet bijv. g₅. Tussen de groepen G en C (zelfde als G) is een bijectieve relatie, dus het klopt inderdaad. In plaatje 2 heeft dan ook elk punt een andere hoogte.

 

De profundis

 rkh, 08-12-2021

 

Over legale routes

Een effectief en humaan immigratiebeleid van de EU had taferelen -zoals aan de Poolse grens- voorkomen, aldus Sacha Kester in het redactioneel commentaar van 10/11. Een stelling die wordt geponeerd, maar verder niet wordt onderbouwd. Ook Arie Elshout ziet in zijn column van 29/11 een legale route als oplossing, hoewel met de nodige kanttekeningen.

 

Wie zijn hoop stelt op legale routes, erkent in ieder geval dat er ook illegale routes zijn. Want anders is de term “legaal” zinledig. En die illegale routes zullen blijven, zolang het aanbod van mensen aan de grenzen van “Fort Europa” groter is dan de “vraag”. Kortom, het aanleggen van legale routes lost helemaal niets op. Ik vind de oplossing van Kester en Elshout dermate absurd en van elke werkelijkheidszin gespeend, dat ik de bewijslast geheel bij hen leg.

r.k.h., 29-11-2021

 

Zijn versleutelde berichten gekraakt?

In de krant stond onlangs, dat de politie erin was geslaagd duizende chat- en mailberichten van Encrochat te ontsleutelen. Je denkt dan dat de politie allerlei mogelijke combinaties heeft uitgeprobeerd en zich uiteindelijk toegang heeft weten te verschaffen of dat de politie de geëncrypte berichten heeft weten te herleiden tot de oorspronkelijke tekst. Mis!

Dat laatste is bij de gebruikte software (AES) schier onmogelijk. En bij een sleutel/password van 16 bytes is het aantal mogelijke combinaties iets in de orde van 10³⁹. En daar komt ook nog eens bij dat elk crimineel duo een eigen sleutel heeft. Je moet dan in dit geval denken aan 1500 klanten met een speciaal geprepareerde blackberry. Het moet dus wel anders zijn gegaan.

 

Maar hoe is het dan wel gegaan? Een belangrijke aanwijzing is –ook in de krant te lezen-: De politie heeft de server gelokaliseerd en –met de machtiging van een Franse rechter- gedurende een maand het beheer overgenomen. Wat is er op de server te zien? Ik neem aan dat de software voor encryptie en decryptie op de server zelf draait en niet op de blackberry’s. Vergelijkbaar met Google. Geef je een zoekopdracht dan vindt de uitvoering plaats op servers ver buiten je gezichtsveld en niet op je eigen ipad, pc of iphone.

 

Wat laat het interne geheugen van de server zien? Zou Pascal de programmeertaal zijn, dan is er de vertaling van “Var a:integer;” naar assembly (een lagere programmeertaal) te zien en van bijv. “read (a)”. De Pascal-opdracht “Var a:integer;” zorgt voor reservering van een geheugenplaats (2 bytes). “Read (a);” haalt input van het toetsenbord en brengt het resultaat naar geheugenvak “a”. Dit geheugenvak moet in het interne geheugen zijn terug te vinden.

 

Wordt de software (AES) aangeroepen om een bericht te versleutelen of te ontsleutelen dan komt op een gegeven moment de vraag om input. Waar die input vandaan komt, interesseert me niet. Het password of de phrase staat daar opeens in al zijn naaktheid. En hebbes!

 

Misschien dat het de politie om de private key te doen was. Maar mijn verhaal blijft hetzelfde: bij de vraag om input moet de crimineel met de billen bloot.

 

Met de encryptie opzich is niets mis. Maar de zwakheid in het systeem is: wie via de rechter of malware het beheer over een server, pc of blackberry weet te krijgen, kan (via de omweg van hacken) codes kraken. Eigenlijk best wel een pover resultaat voor uren nadenken.

 

rkh, 19-10-2021

 

Groei (2)

De vraag is en was: Is groei van de economie innerlijke noodzaak?

 

Bij de beantwoording van die vraag ben ik uitgegaan van het Rijnlandsmodel. Dat model kun je bevragen, maar dat is uitgangspunt en staat dus niet ter discussie. Het gaat hier om een simpele als/dan-redenering.

 

Mijn stelling is: Als er geen groei (in termen van nieuwe producten en diensten) is, dan stort de economie in. Dus groei als noodzakelijke voorwaarde.

Of omgekeerd (modus tollens): “Kapitalisme” è groei. Dat lijkt een platitude, een analytische waarheid, en dus een cirkelredenering. Alsof er geen missing link is, alsof er verder niets te verklaren is.

 

Die missing link –het onderliggend mechanisme- heb ik gevonden in het wezen van concurrentie, nl. dat concurrentie zichzelf opheft. En dat dwingt ondernemers te innoveren, om zo concurrerend te blijven.

 

Je zou ook kunnen zeggen: “Gejaagd door de winst”.

 

rkh, 29-08-2021

 

 

Groei

Is groei van de economie innerlijke noodzaak? In de zin dat bij afwezigheid van groei de economie zichzelf “opheft”?

 

Concurrentie in een gereguleerde markt is in onze economie het onderliggend principe. Concurrentie zorgt voor technologische, organisatorische en financiële innovaties en voor producten en diensten voor een betaalbare prijs. Voor ondernemers is het hollen om niet te vallen.

Regulatie moet er voor zorgen, dat het er daarbij fair aan toegaat. Om die reden zijn bijv. kartels verboden en worden monopolies bestreden.

 

Zonder de mogelijkheid van groei, zonder de mogelijkheid nieuwe producten en diensten in de markt zetten, valt de concurrentie dood. Want concurrentie op prijs gaat altijd voor laagste prijs t.o.v. de concurrenten, tot de winst nul is. Concurrentie heft zichzelf op. En wanneer er niets meer te verdienen is, valt de economie stil.

 

r.k.h., 19-08-2021

Alexander vs Akwasi

Stel het is Prinsjesdag en iemand in een oranje uitdossing staat met een bord langs de route met daarop: “Weg met de Monarchie!”. Dat is grappig, omdat je dat van een Oranjeklant niet verwacht, die is immers per definitie vóór het koningshuis. Het wordt nog grappiger wanneer bijv. Derksen in de uitzending van Veronica Inside de vraag stelt: “Weten we wel zeker dat dat niet Alexander is!”. Van de koning verwacht je al helemaal niet, dat hij tegen de monarchie is.

 

De meesten zullen de grap waarderen. Dat is geheel anders bij de grap van Derksen over Akwasi. Hoewel beide grappen dezelfde opbouw hebben.

 

In juni 2020 is er in Leeuwarden een demonstratie van Black Lives Matter. In beeld verschijnt een zwarte Piet in vol ornaat met een kartonnetje met daarop “Zwarte Piet lives matter”. Waarop Derksen zich in Veronica Inside hardop afvraagt of dat niet Akwasi zelf is. Ik vind het grappig vanwege de verrassende omkering: Akwasi is nu eens vóór zwarte Piet.

 

In de opmerking van Derksen zit nog een omkering: Akwasi wordt niet vergeleken met Zwarte Piet –wat naar de normen van nu onfatsoenlijk of zelfs racistisch mag heten-, maar omgekeerd: Zwarte Piet wordt met Akwasi vergeleken. En dat maakt nogal uit. Om een helder voorbeeld te geven: het maakt nogal uit of ik mezelf met Einstein vergelijk of dat ik Einstein met mezelf vergelijk.

Deze subtiele omkering is niet opgepikt. In tegenstelling tot wat velen dachten te horen of wilden horen, zegt of suggereert Johan Derksen dus nergens dat Akwasi zwarte Piet is!

 

r.k.h., 03-08-2021

 

“Jongeren”

Is er iets ergs gebeurd, waarbij (vooral) jongeren uit een bepaalde bevolkingsgroep zijn betrokken, dan hebben de Mainstream Media het over “jongeren”. Zogenaamd om de stigmatisering van die bepaalde bevolkingsgroep te voorkomen, maar wat vooral de maatschappelijke vrede moet dienen. De insteek is hier dus niet moreel, maar pragmatisch.

Zelfs De Telegraaf heeft zich onderworpen aan de zgn. Code van Bordeaux.

Een subgroep (“die het al zo moeilijk heeft”) stigmatiseren door de etniciteit van de daders bekend te maken, mag dus niet. Maar de rest (alle jongeren in Nederland minus bijv. Marokkaanse Nederlanders) stigmatiseren door hen de schuld in de schoenen te schuiven, mag kennelijk wel. Waar dus vooral andere subgroepen bijv. jongeren met Turkse roots last van hebben, want die worden ten onrechte en onnodig van alles en nog wat verdacht. Dat is dan collateral damage!

 

Van de omertà –het niet willen benoemen- hebben de Marokkaanse Nederlanders zelf nog het meeste last. Want hoevelen zullen niet aan juist die subgroep hebben gedacht bij het nieuws over Mallorca, waar een Nederlander door andere Nederlanders in koelen bloede dood is getrapt?

 

“Sagen, was ist”. Dat was de slogan van Rudolf Augstein als hoofdredacteur van het weekblad Der Spiegel. Die slogan zou de code van Bordeaux over moeten nemen.

 

Nota bene: Het is een klein wonder dat de term “Mocro Mafia” algemeen geaccepteerd is. Voor zolang als dat duurt natuurlijk.

 

r.k.h., 28-07-2021

 

 

Mees en de bitcoin

 Bij het creëren van bitcoins uit het niets –het zogenaamde minen- worden “complexe wiskundige vergelijkingen” opgelost, aldus Heleen Mees in haar column van 30/6. Je denkt dan algauw “Poeh Poeh, wat knap!”. Maar ik vind het zelf verre van knap. Ik zou ook niet weten waar Mees het over heeft en ze weet het waarschijnlijk zelf ook niet.

Op de tekst van Mees kun je een algoritme (een sofware-programma) loslaten dat een getal oplevert. Dat algoritme moet zo knap in elkaar zitten, dat zelfs de kleinste wijziging in de tekst een ander getal oplevert. Bitcoin maakt gebruik van het algoritme Hash256, dat meer dan 10⁷⁵ mogelijke uitkomsten oplevert. Dus dat 2 kopieën van de tekst van Mees met elk 1 wijziging eenzelfde getal –de zgn. hash- opleveren is wel erg klein.

De opdracht aan de miners –de delvers van het digitale goud- is nu bij een tekst met transactiegegevens een hash te vinden die kleiner is dan een bepaald getal (hoe kleiner dit getal hoe moeilijker het wordt). Wie het eerst aan de eis voldoet, krijgt de pot. Het gaat zo: Aan de tekst met transacties wordt in het veld nonce (number used only once) een willekeurig getal gezet. Je berekent de hash. Wordt niet aan de eis voldaan dan vul je de opvolger in. Etc. Na ongeveer 10 minuten heeft iemand –waar ook ter wereld- “het probleem” opgelost. Gaat het te snel dan wordt de eis verhoogd. Ik zou zeggen: “Dommer kan het niet”.

 r.k.h, 30-06-2021