NL1011719C2 - Werkwijze voor het met toepassing van een functie en een sleutel vercijferen van een reeks symbolen. - Google Patents

Description

Titel: Werkwijze voor het met toepassing van een functie en een sleutel vercijferen van een reeks symbolen.

De uitvinding heeft betrekking op een werkwijze volgens de aanhef van conclusie 1.

Een werkwijze van deze soort is bekend uit EP-A-0399587. Bij de bekende werkwijze bestaat de voor het vercijferen toegepaste functie 5 uit een niet-lineaire functie die gevormd wordt door een substitutietabel ("S-box") die afhankelijk van de sleutel gegenereerd wordt. Het document geeft geen verdere beschrijving van de wijze waarop de substitutietabel gegenereerd wordt. Voor het verkrijgen van goede statistische eigenschappen van de uitvoer van de 10 substitutietabel ten opzichte van variabele invoer wordt een door toepassing van de substitutietabel verkregen reeks symbolen gecombineerd met een even lange reeks van statistisch goed gespreide symbolen. De reeks symbolen die daarbij verkregen wordt kan gebruikt worden voor het vercijferen van een te vercijferen 15 ingangssymbolenreeks in een vercijferde uitgangssymbolenreeks. Door toepassing van een sleutelafhankelijke substitutietabel in plaats van een vaste substitutietabel wordt het vercijferingsalgoritme versterkt.

De bekende werkwijze heeft als bezwaar dat wanneer in hoofdzaak steeds dezelfde sleutel gebruikt wordt de genoemde versterking van het 20 vercijferingsalgoritme in de praktijk aanzienlijk teniet gedaan wordt. Dit kan zich bijvoorbeeld voordoen bij autenticatie bij gebruik van een chipkaart, zoals een telefoonkaart en een GSM-kaart.

De uitvinding beoogt de bezwaren van de bekende werkwijze op te heffen. Daartoe verschaft de uitvinding een werkwijze als beschreven 25 in conclusie 1.

De verzender van de vercijferde uitgangssymbolenreeks en de ontvanger van deze reeks moeten beide de beschikking hebben over dezelfde sleutel en de voor het vercijferen gebruikte ingangssymbolenreeks, althans het gedeelte van laatstgenoemde reeks 30 dat gebruikt werd voor het wijzigen van de functie. Hierdoor is de werkwijze in het bijzonder geschikt voor authenticatie, waarbij de ontvanger van een vercijferde symbolenreeks kan controleren of een verzender met een aan de ontvanger gesuggereerde identiteit een bijpassende sleutel gebruikt heeft en bij een positieve uitkomst van 35 deze controle de identiteit van de verzender voor de ontvanger verzekerd is.

101 1719 - 2 -

De symbolenreeks die gebruikt wordt voor het wijzigen van de functie is in het bijzonder variabel en is bijvoorbeeld een per sessie opgewekt uitdaaggetal ("challenge number"), een (ander) willekeurig getal, of een variabele attribuut van de verzender, zoals een op een 5 chipkaart bij gehouden saldo.

Wanneer de voor het vercijferen gebruikte niet-lineaire functie een inverteerbare functie was kan de ontvanger van de vercijferde symbolenreeks de genoemde controle uitvoeren met gebruik van dezelfde functie, dezelfde sleutel en de ontvangen symbolenreeks als invoer 10 voor de functie. Het resultaat moet gelijk zijn aan de voor het vercijferen gebruikte ingangssymbolenreeks.

Omdat de ontvanger de bij het vercijferen gebruikte ingangssymbolenreeks kent kan de ontvanger de controle ook uitvoeren door dezelfde bewerkingen uit te voeren als door de verzender gedaan 15 zijn, waarbij de door de ontvanger ontvangen reeks gelijk moet zijn aan de door de ontvanger opgewekte reeks. In dat geval is het geen eis dat de functie een inverteerbare functie is, waardoor bij gelijk blijvende complexiteit een sterker vercijferingsalgoritme gerealiseerd kan worden dat beter bestand is tegen aanvallen.

20 De voor het vercijferen toegepaste functie is bij voorkeur een niet-lineaire functie die gevormd kan worden door een substitutietabel of een cryptografische functie, zoals een functie waarbij afhankelijk van de invoer en de sleutel bepaalde bewerkingen al of niet uitgevoerd worden.

25 Verdere eigenschappen en voordelen van de uitvinding zullen blijken uit de hierna volgende toelichting van uitvoeringsvormen van de uitvinding in combinatie met de bijgevoegde tekeningen, waarin: fig. 1 een schema toont van een bekend vercijferingsalgoritme; fig. 2 een schema toont van een eerste uitvoeringsvorm van de 30 uitvinding; fig. 3 een stroomdiagram toont voor de werking van de uitvoeringsvorm volgens fig. 2; en fig. 4 een andere uitvoeringsvorm van de uitvinding toont.

In fig. 1 is door middel van een blok 1 een bekend 35 vercijferingsalgoritme (of encryptie-algoritme) voorgesteld. Het vercijferingsalgoritme maakt gebruik van één of meer, eveneens door blokken voorgestelde functies 2. Uitgaande van een te vercijferen ingangssymbolenreeks IN 3 bepaalt het vercijferingsalgoritme met 101 17 1 9 - 3 - behulp van een geheime sleutel 4 een vercljferde uitgangssymbolenreeks UIT 5. Het bekende vercijferingsalgoritme DES werkt volgens dit principe, waarbij acht niet-lineaire functies gebruikt worden die gevormd worden door substitutietabellen ("S-boxes"). De uitvinding is 5 echter niet beperkt tot het DES algoritme en is ook niet beperkt tot het gebruik van niet-lineaire functies en van substitutietabellen voor de functies.

Fig. 2 toont een schema van een op het vercijferingsalgoritme van fig. 1 gebaseerd vercijferingsalgoritme 7 volgens de uitvinding.

10 De functies zijn aangegeven met verwijzingscijfer 8. De functies 8 zijn te wijzigen door toepassing van een bijbehorend wijzigingsalgoritme 9 op basis van de ingangssymbolenreeks IN 3 of een gedeelte daarvan. De wijzigingsalgoritmen 9 hoeven niet gelijk te zijn.

15 Hierna zal met verwijzing naar het stroomdiagram van fig. 3 de werking van het vercijferingsalgoritme van fig. 2 toegelicht worden.

Een wijzigingsalgoritme 9 wijzigt de functie 8 op basis van een wijzigingssymbolenreeks die initieel van de ingangssymbolenreeks IN 3 afgeleid wordt (blok 11). Het wijzigen van de functie 8 vindt plaats 20 in een aantal stappen, te weten de stappen n = 0 t/m n - Nmax, waarbij Nmax vast of ook afhankelijk van bijvoorbeeld de reeks IN 3 kan zijn. Daarom wordt bij aanvang van het wijzigen van de functie 8 een stappenteller naar 0 geïnitialiseerd (blok 12). Vervolgens wordt de functie 8 op basis van de waarde van n en de wijzigingsreeks gewijzigd 25 (blok 13). Vervolgens wordt het aantal getelde stappen met 1 verhoogd (blok 14). Vervolgens wordt gecontroleerd of de functie 8 reeds het maximum aantal keren gewijzigd is (blok 15). Wanneer aan deze voorwaarde voldaan is is het wijzigen van de functie 8 ten einde en anders wordt de wijzigingssymbolenreeks gewijzigd (stap 16) en wordt 30 op basis van de nieuwe waarde van n en de gewijzigde wijzigingssymbolenreeks de functie 8 opnieuw gewijzigd (stap 13). In de hierna volgende Tabel I is een voorbeeld gegeven voor de werking van het in fig. 2 getoonde vercijferingsalgoritme 7.

1011719

- 4 -TABEL I

stap wijzigings- vanaf stap n - O

n symbolenreeks verwissel y(nmod8) en y(x(0)) voor n>0 x(2): - (x(0) + x(l))mod8 - i 01234567 x(0) x(l) x(2) y(i) 30576412 0 523 40576312 1 237 45076312 2 375 45706312 3 752 45726310 4 524 45723610 5 247 45623710 6 476 45621730 7 763 45621730 8 635 15624730 9 351 12654730

Er wordt aangenomen dat de symbolenverzameling acht symbolen omvat, die in de Tabel weergegeven zijn met de cijfers 0 t/m 7. Verder wordt aangenomen dat de functie 8 gevormd wordt door een substitutietabel. Deze tabel kan gerealiseerd worden door een 5 herschrijfbaar geheugen met acht geheugenlocaties met adressen of rangnummers i - 0...7. De geheugenlocaties bevatten elk een van de symbolen, waarbij elk symbool slechts eenmaal in de geheugenlocaties voorkomt. In Tabel I is de inhoud van een geheugenlocatie met adres of rangnummer i aangegeven met y(i). Initieel bevatten de 10 geheugenlocaties voor i - 0...7 respectievelijk de symbolen 3, 0, 5, 7, 6, 4, 1, 2. Deze reeks symbolen vormt een initiële substitutietabel. Een symbool van een te vercijferen symbolenreeks wordt beschouwd als adres of rangnummer i en wordt vervangen door het symbool in de geheugenlocatie met dat adres. Volgens de initiële 101 1719 - 5 - substitutietabel van Tabel I wordt dus bijvoorbeeld 0 vervangen door 3, 1 door 0, 2 door 5.....7 door 2.

Alvorens een te vercijferen symbolenreeks vercijferd wordt, wordt volgens de uitvinding eerst de initiële substitutietabel 5 gewijzigd. Volgens het voorbeeld van Tabel I gebeurt het wijzigen in tien stappen (stap n - 0 t/m n - Nmax). De wijziging vindt plaats afhankelijk van de symbolen van de te vercijferen symbolenreeks, althans van een aantal symbolen daarvan. In Tabel I zijn de te vercijferen symbolen die gebruikt worden voor het wijzigen van de 10 substitutietabel de bij stap n - 0 aangegeven symbolen 5, 2 en 3. Deze symbolen worden toegewezen aan respectieve variabelen x(0), x(l) en x(2).

Tijdens de eerste stap met n = 0 wordt het symbool y(n), dat wil zeggen het symbool 3 van geheugenlocatie 0, verwisseld met het symbool 15 y(x(0)), te weten symbool 4 van locatie x(0) -5. In Tabel I zijn voor de duidelijkheid voor elk van de tien stappen n — 0 ... 9 de verwisselde symbolen van de substitutietabel van acht symbolen onderstreept.

Vervolgens wordt een hulpvariabele h berekend die gelijk is aan: 20 h - (x(0) + x(l)) modulo (het aantal mogelijke symbolen), of in het voorbeeld h - (x(0) + x (1)) modulo 8.

Vervolgens worden de symbolen van de wijzigingssymbolenreeks x(0), x(l) en x(2) als volgt vervangen (":«" betekent "wordt”, dat wil 25 zeggen een toewijzing).

x(0): - x(l), x(l): - x(2), en x(2): - h.

Het voor elke stap verwisselen van symbolen op basis van het 30 stapnummer en de symbolen van de wijzigingssymbolenreeks wordt een geschikt aantal keren herhaald, in het voorbeeld van Tabel I Nmax + 1 - 10 keer. Aan het einde van dit wijzigingsalgoritme is de initiële substitutietabel: 3, 0, 5, 7, 6, 4, 1, 2 35 vervangen door een uiteindelijke substitutietabel: 1, 2, 6, 5, 4, 7, 3, 0.

Vervolgens kunnen de symbolen van een ingevoerde te vercijferen reeks in overeenstemming met de rangschikking van de symbolen in de 101 1719 - 6 - uiteindelijke substitutietabel vervangen worden voor het leveren van een uitgaande vercijferde symbolenreeks. Hierdoor worden in het voorbeeld de reeks ingevoerde symbolen 5, 2, 3 vervangen door respectievelijk 7, 6, 5. Deze uitgaande symbolenreeks wordt voor 5 eventuele verdere stappen van het vercijferingsalgoritme gebruikt.

Fig. 4 toont het schema van een vercijferingsalgoritme 18, dat van de vercijferingsalgoritme 5 van fig. 2 verschilt doordat het wijzigingsalgoritme 9 vervangen is door een wijzigingsalgoritme 19.

• Het wijzigingsalgoritme 19 is, net als het wijzigingsalgoritme 9, 10 afhankelijk van een aantal te vercijferen symbolen IN 3, maar bovendien van een aantal symbolen van de sleutel 4.

Tabel II geeft een voorbeeld van de werking van het wijzigingsalgoritme 19.

TABEL II

stap wijzigings- vanaf stap n - 0 n symbolenreeks verwissel y(nmod8) voor n>0 en y(x(0)) x(2):-(x(0) + x(l))mod8 - i 01234567 x(0) x(2) x(4) y(i) 30576412 x(l) x(3) 0 52324 40576312 1 23247 45076312 2 32475 45706312 3 24755 45076312 4 47556 45076312 5 75563 45076213 6 55635 45076123 7 56352 45076321 8 63523 25076341 9 35231 27056341

II I

Tabel II verschilt van Tabel I slechts doordat de wijzigingssymbolenreeks x(0), x(l), x(2) aangevuld is met x(3), x(4).

10117 1 9 - 7 -

De symbolen x(3) en x(4) zijn afgeleid van de sleutel 4. In het voorbeeld van Tabel II is de initiële wijzigingssymbolenreeks 5, 2, 3, 2, 4. De uiteindelijke substitutietabel is volgens Tabel II: 2, 7, 0, 5, 6, 3, 4, 1.

5 De ingevoerde symbolenreeks IN 3 met de symbolen 5, 2, 3 wordt in overeenstemming met deze uiteindelijke substitutietabel vervangen door de vercijferde uitgangssymbolenreeks UIT 20 met de symbolen 3, 0, 5.

De symbolen van de initiële substitutietabel kunnen willekeurig 10 gerangschikt zijn, zolang zowel de zender van een vercijferde symbolenreeks UIT 5 en de ontvanger van de vercijferde symbolenreeks dezelfde initiële substitutietabel gebruiken. Wanneer aan deze voorwaarde steeds voldaan kan worden kan het vercijferingsalgoritme versterkt worden door als initiële substitutietabel een 15 substitutietabel te gebruiken die tijdens een voorgaand vercijferingsproces gebruikt is, bijvoorbeeld de laatst gebruikte uiteindelijke substitutietabel. Wanneer het gevaar bestaat dat niet steeds aan de genoemde voorwaarde voldaan wordt, kan erin voorzien worden dat de ontvanger van de vercijferde symbolenreeks 5 een aantal 20 van dergelijke voorgaande substitutietabellen onthoudt en een oudere daarvan gebruikt wanneer het ontcijferen van de ontvangen reeks tot een negatief controleresultaat leidt.

Doordat zowel tijdens het vercijferen van een reeks symbolen als tijdens het ontcijferen daarvan de gebruikte sleutels gelijk moeten 25 zijn en kennis aanwezig moet zijn van de vercijferde reeks symbolen IN 3 kan de ontvanger van de vercijferde reeks precies dezelfde bewerking, te weten een vercijfering, uitvoeren als de ontvanger gedaan heeft en de resultaten met elkaar vergelijken. In dat geval kan voor de functie een niet-inverteerbare functie gebruikt worden die, 30 bij gelijk blijvende complexiteit, een sterker vercijferingsalgoritme mogelijk maakt.

De in combinatie met de Tabellen I en II toegelichte wijzigingsalgoritmen dienen slechts als voorbeeld. Voor het wijzigen van de wijzigingssymbolenreeks kunnen bijvoorbeeld voor elke stap meer 35 dan twee en/of een verschillend aantal modulo optellingen toegepast worden en kunnen de symbolen van de wijzigingsreeks op andere wijzen geherrangschikt worden in plaats van door middel van een eenvoudige verschuiving.

10117 1 9

Claims (8)

1. Werkwijze voor het met toepassing van een functie (2, 8) en afhankelijk van een sleutelsymbolenreeks (4) vercijferen van een ingangssymbolenreeks (3), omvattende: 5 het door middel van een wijzigingsalgoritme en afhankelijk van een wijzigingssymbolenreeks wijzigen van de functie; het aan de gewijzigde functie onderwerpen van de ingangssymbolenreeks voor het afhankelijk van de sleutelsymbolenreeks bepalen van een uitgangssymbolenreeks (5, 20), 10 met het kenmerk, dat het wijzigingsalgoritme (9, 19) een aantal sequentiële stappen omvat, waarbij in elke stap de functie (8) afhankelijk van de wijzigingssymbolenreeks gewijzigd wordt en na elke stap de wijzigingssymbolenreeks door middel van een subalgoritme gewijzigd wordt, waarbij voor de eerste stap (n - 0) als 15 wijzigingssymbolenreeks een initiële wijzigingssymbolenreeks gebruikt wordt die van de ingangssymbolenreeks (3) afgeleid wordt.

2. Werkwijze volgens conclusie 1, met het kenmerk, dat de Initiële wijzigingssymbolenreeks tevens van de sleutelsymbolenreeks (4) 20 afgeleid wordt.

3. Werkwijze volgens conclusie 1 of 2, met het kenmerk, dat het wijzigingsalgoritme (9, 19) het vervangen omvat van een symbool van de wijzigingssymbolenreeks door een vervangend symbool dat verkregen 25 wordt door een optelling van twee of meer symbolen van de wijzigingssymbolenreeks modulo het aantal mogelijke verschillende symbolen.

4. Werkwijze volgens een voorgaande conclusie, met het kenmerk, dat 30 het wijzigingsalgoritme (9, 19) het wijzigen van rangnummers omvat van twee of meer van de symbolen van de wijzigingssymbolenreeks.

5. Werkwijze volgens een voorgaande conclusie, met het kenmerk, dat voor het wijzigen van de functie als initiële functie de functie 35 gebruikt wordt die eerder gebruikt werd voor het bepalen van een eerdere uitgangssymbolenreeks (5, 20). 101 1719 - 9 -

6. Werkwijze volgens een voorgaande conclusie, met het kenmerk, dat de functie een substitutiefunctie is.

7. Werkwijze volgens een van de conclusies 1 t/m 5, met het 5 kenmerk, dat de functie een niet-inverteerbare functie is.

8. Werkwijze volgens een van de voorgaande conclusies, met het kenmerk, dat de functie een substitutietabel ("S"-box) omvat die vervangende symbolen voor de symbolen van de ingangssymbolenreeks 10 bevat, en het wijzigingsalgoritme het afhankelijk van de wijzigingssymbolenreeks verwisselen van twee of meer symbolen van de substitutietabel omvat. 10117 1 9