[Algoritme] Key achterhalen

[Dennis27]

Momenteel ben ik bezig met het 'oplossen' van een aantal crypto puzzels. Eén daarvan is een simpel lineair algoritme. Stel we nemen het woord 'hallo'. Van elk karakter nemen we de ascii waarde

h = 104
a = 97
l = 108
l = 108
o = 111

En we verzinnen een numerieke key...stel key = 555

Nu gaan we het woord hallo versleutelen als volgt:

ciphertext = (ciphertext + asciiwaarde_van_letter_i ) * key

De ciphertext wordt dus een erg groot getal (bij grote keys). In dit geval wordt het:

ciphertext = ((((((((104*555)+97)*555)+108)*555)+108)*555)+111)*555 = 5485660802282430

Met dit gegeven kun je de originele letters weer terugvinden als je de key hebt. De grap in die puzzels is dat die key onbekend is, en die moet je dus eerst zien te vinden. Nu zijn er 3 puzzels, met toenemende grootte van de key. Eén manier om te key te vinden is door het 'brute forcen'. Echter er schijnen twee andere manieren te zijn die zelfs een groot cipertext getal kunnen decrypten in een paar minuten. Dit schijnt te kunnen door goed naar het algoritme te kijken en gebruik te maken van wiskundige kennis.

Nou wiskundig is het gewoon iets van:

ciphertext = (ciphertext + c[i] ) * key , waarbij c[i] het i-de karakter is uit de plaintext c.

Je weet alleen de uiteindelijke ciphertext...en verder niets...

Hoe is dit op te lossen? Iemand een idee?

Ik weet helaas veel te weinig van getaltheorie om daar iets nuttigs over te vertellen. Een 'nette methode' werkt niet bij dat soort reusachtige getallen.

[Dennis27]

Het schijnt dat je het kunt doen met de hand en een big number calculator....

Sowieso kun je (jouw voorbeeld iig) het omschrijven tot:

104/(555^0) + 97/(555^1) + 108/(555^2) + 108/(555^3) + 111/(555^4) = 5485660802282430/(555^4)

dit is in ieder geval een `simpele'sommatie.



Ik begrijp niet zo goed wat je wél weet van tevoren...

[Dennis27]

Er zijn 2 dingen die we weten:

1) De uiteindelijke ciphertext; in mijn voorbeeld dus 5485660802282430

2) Het algoritme

Het 'decrypt' algoritme is simpelweg:
- c1 = deel de ciphertext door de key
- c2 = bereken de modulus van de ciphertext en de key: c1 % key
- zet dit verkregen nummer om naar het ascii teken
- trek deze asciiwaarde van de ciphertext af: c3 = c1 - c2
c3 is dan die 'nieuwe' ciphertext nadat we één karakter gevonden hebben. Het algoritme herhaalt zich nu weer (c1 = c3 / key...etc), totdat de plaintext 0 is.

wtf

[ILUsion]

Ik zou in ieder geval proberen om te ontbinden in factoren, het probleem opslitsen in deel problemen eigenlijk. Zo kun je proberen de key te achterhalen (er zijn twee mogelijkheden per priemfactor: ofwel bepaalt de factor de key ofwel bepaalt de factor de cyphertext). Binnen die cyphertext moet je natuurlijk weer net hetzelfde doen en dezelfde key proberen te vinden (dus ook weer ontbinden in priemfactoren).

Volgens mij moet je er zo wel geraken, na een hele tijd rekenen.

[Dennis27]

ILUsion schreef op 07-04-2006 @ 20:17 :
Ik zou in ieder geval proberen om te ontbinden in factoren, het probleem opslitsen in deel problemen eigenlijk. Zo kun je proberen de key te achterhalen (er zijn twee mogelijkheden per priemfactor: ofwel bepaalt de factor de key ofwel bepaalt de factor de cyphertext). Binnen die cyphertext moet je natuurlijk weer net hetzelfde doen en dezelfde key proberen te vinden (dus ook weer ontbinden in priemfactoren).

Volgens mij moet je er zo wel geraken, na een hele tijd rekenen.

Als de ciphertext 200 nummers is gaat het ontbinden niet zo snel? Ik snap niet zo goed wat je precies bedoelt denk ik...zou je dat eens kunnen uitleggen aan de hand van een simpel rekenvoorbeeldje?

[ILUsion]

Tja, het ontbinden gaat natuurlijk niet op 1-2-3, maar ontbinden in factoren (priemfactoren meerbepaald), doe je door de deelbaarheid van het getal door de verschillende priemgetallen na te gaan.

Een eenvoudig rekenvoorbeeld:
100: 2 x 2 x 5 x 5 (je begint dus bij het laagste priemgetal, als dat niet meer deelbaar is, dan ga je naar het volgende (3), dat is geen deler, dus ga je naar het volgende (5) en dat is weer wel een deler).

3234: 2 x 3 x 7 x 7 x 11

In combinatie met wat Pieter_de_man zegt, laat het me ook een voorwaarde bedenken voor welke priemfactoren niet tot de sleutel behoren: een priemfactor kan slechts behoren tot de sleutel als hij meer dan n+1 keer voorkomt in een cyphertext van n tekens.

En priemfactoren die in de ASCII-reeks tussen "A" (65, geloof ik) en "z" (nummer weet ik niet vanbuiten) liggen, zijn bij eenmalg voorkomen een letter van de reeks.

Verder nog een gedachtenspinsel, ook veroorzaakt door hetgeen Pieter_de_man neerschrijft: het lijkt verdacht veel op een conversie van getallenstelsel (bijvoorbeeld binair -> decimaal, maar dan van het tiendelig -> het key-delig stelsel -> ASCII). Misschien valt daar ook wel iets mee te doen (ik ken maar een beperkt deel van de getallentheorie, maar misschien heb jij daarover wel meer kennis?)

[Dennis27]

Ik heb 1 van de 3 puzzels opgelost (die met de kleinste key) d.m.v. het brute forcen van de key. En deze key was geen priemgetal, dus als ik de deelbaarheid wil testen is het delen door verschillende priemgetallen niet nuttig, omdat je zo de key niet vindt?

Ook al kun je verder weinig met zo'n zwak algoritme, ik vind het op dit moment interessant omdat ik niet wist dat je het ook bij hele lange keys zo kunt oplossen door wat gegoochel met wiskunde. Maar op dit moment heb ik nog geen idee hoe...

ILUsion: De key kan uiteraard ook een priemgetal zijn, dus ik zal dat zeker gaan testen...you never know

Bijv de ciphertext = ((((((((104*key)+97)*key)+108)*key)+108)*key)+111).....kun je ook schrijven als 104*key^4 + 97*key^3 + 108*key^2 + 108* key + 111 ..dit lijkt inderdaad op een getallenstelsel met als base 'key'

[ILUsion]

Je begrijpt me verkeerd: ik zeg niet dat de key een priemgetal is, maar de werkwijze waarop ik steun ligt er gewoon in dat elk getal ofwel een product van priemgetallen is of een priemgetal. Dat volgt uit de definitie van een priemgetal (en dan vooral wat geen priemgetal is).

De key uit je voorbeeld ( 555 ) is zo bijvoorbeeld 3 x 5 x 37. Zoals je ziet allemaal priemgetallen. Waarom ik dat onderverdelen doe: het is vaak makkelijker met kleinere getallen te werken.

Ik zie nu verder ook iets anders (met wat meer op het algoritme in te kijken): de key krijg je niet direct en is ook niet direct voor de hele string zichtbaar (zoals ik eerder schreef, met die n en n+1 daar). Uit die priemfactoren die verschijnen, kun je de sleutel composeren; het grootste priemgetal mag je normaalgezien vergeten. In dat opzicht berust het ook wel op bruteforcen, maar op een meer intelligente manier (toch ook nog met heel wat mogelijkheden voor de sleutel hoor, maar minder dan alles één per één af te gaan.

En dan moet je natuurlijk de decryptie van het laatste symbool bekijken (cyphertext % key, dus) en die meten met haalbaarheid in ASCII-reeks. Afhankelijk daarvan kun je zien of de key te groot of te klein is natuurlijk

Tip: voor het ontbinden in priemfactoren, kun je het makkelijkst Derive, Mathematica, ... gebruiken. Vermits de laatste factor steeds zeer groot zal zijn (en je dus tijd zou kunnen verspillen aan die te controleren op deelbaarheid).

[Dennis27]

Klinkt interessant, maar volgens mij snap ik het nog niet helemaal...
Stel de ciphertext is een nummer van 200 getallen. Vervolgens ga ik kijken door welke priemgetallen dit nummer deelbaar is. Daarvoor heb ik Mathematica tot m'n beschikking En dan? Stel de key zou 555 zijn. Betekent dit dat de ciphertext dan deelbaar is door 3, 5 en 37? En stel ik vind dat de ciphertext deelbaar is door 37. Hoe ga je dan verder? Als het idee me duidelijk is, dan kom ik er wel, want de implementatie maken met Mathematica of bijv Java is het probleem niet

[ILUsion]

Dennis27 schreef op 08-04-2006 @ 16:40 :
Klinkt interessant, maar volgens mij snap ik het nog niet helemaal...
Stel de ciphertext is een nummer van 200 getallen. Vervolgens ga ik kijken door welke priemgetallen dit nummer deelbaar is. Daarvoor heb ik Mathematica tot m'n beschikking En dan? Stel de key zou 555 zijn. Betekent dit dat de ciphertext dan deelbaar is door 3, 5 en 37? En stel ik vind dat de ciphertext deelbaar is door 37. Hoe ga je dan verder? Als het idee me duidelijk is, dan kom ik er wel, want de implementatie maken met Mathematica of bijv Java is het probleem niet

Het is enkel als versnelling om te bruteforcen: als je die delers hebt, dan kun je proberen die te combineren, je weet in welke range je tekens moeten liggen (= cypertext % key), die zoals je zegt de modulo moet zijn van je gekozen key met de gehele cypher. In dat opzicht is het nog steeds wel bruteforce, maar iets intelligenter zoeken naar een key. Volgens mij bestaat er niet echt een methode om direct key en boodschap te construeren uit een getal, maar met die range [65, ..] (of desnoods [0,255]), moet wel iets te doen vallen op dat gebied.

[Dennis27]

ILUsion schreef op 09-04-2006 @ 18:09 :
Het is enkel als versnelling om te bruteforcen: als je die delers hebt, dan kun je proberen die te combineren, je weet in welke range je tekens moeten liggen (= cypertext % key), die zoals je zegt de modulo moet zijn van je gekozen key met de gehele cypher. In dat opzicht is het nog steeds wel bruteforce, maar iets intelligenter zoeken naar een key. Volgens mij bestaat er niet echt een methode om direct key en boodschap te construeren uit een getal, maar met die range [65, ..] (of desnoods [0,255]), moet wel iets te doen vallen op dat gebied.

Thnx voor je idee. Ik ga het proberen en laat nog wel weten of dit succesvol is

[Dennis27]

Deze 'slimme' brute force heeft me uiteindelijk de juiste key opgeleverd Nu maar gaan nadenken over de derde manier die hele lange keys kan vinden...

[Integer]

Misschien moet je eens zo'n heerlijk college algebra gaan volgen!

http://www.math.leidenuniv.nl/~reinier/syllalg1.pdf

[Dennis27]

Methode 3 heeft een hele lange key, maar ik las steeds over iets heen dat wel degelijk van belang is nu. En dat is dat ik weet dat de originele tekst bestaat uit 32 karakters (tis een MD5 hash).

Dat deed me direct weer denken aan dat getallenstelsel:

cipher = a1*key^32 + a2*key^31 + a3*key^30 + ... + a31*key²+a32*key

Hmmz