NO321423B1 - Fremgangsmate for asymmetrisk, kryptografisk kommunikasjon, samt tilhorende baerbar gjenstand - Google Patents

Abstract

I en asymmetrisk kryptografisk kommunikasjonsprosess etableres en korrespondanse mellom en første verdi (x) representert ved n elementer (xi) i en ring (A) og en andre verdi (y) representert ved m elementer (yi...ym) i denne ringen, idet n og m er heltall som er større enn eller lik 2. Korrespondansen er definert ved fiervariable offentlige polynomer (P) på AA, med en lav total grad, slik at det finnes likninger av typen Pi(x,.... x„; Yi..Y; Zi...Z)0, hvor ( Zu ..Zer mulige mellomliggende variabler og k er et heltall. Videre er ihvertfall hoveddelen av polynomene (P) ikke på formen T(yY) = S(x...x,) hvor Si-ene ville være polynomer med total grad 2 og Tene ville være polynomer med total grad 1. Oppfinnelsen angår også et tilhørende bærbart objekt.

Description

1. - INNLEDNING

Foreliggende oppfinnelse angår en fremgangsmåte for asymmetrisk kryptografisk kommunikasjon for å prosessere meldinger samt å beskytte kommunikasjon mellom kommunisatorer. Den kan anvendes for å kode meldinger på en asymmetrisk måte, eller for å signere dem på samme asymmetriske måte. Den kan også anvendes til asymmetrisk autentifikasjon.

Denne fremgangsmåten anvender to nye familier av algoritmer som betegnes «Dragon» og «Kjeder (Chains)». Disse to familiene kan også kombineres.

Det som gjør disse nye algoritmene spesielt fordelaktige er at noen av dem er : 1. enkle å anvende i lavspennings-chipkort; 2. «En-veis (ONE-WAY TRAPDOOR)»-bijeksjoner, dvs. bijeksjoner som er funksjoner for koding med offentlige nøkler; 3. dessuten, bijeksjoner på veldig korte variabler (for eksempel på 64

eller 128 bits).

Disse «Dragon»- og «Kjede(Chains)«-algoritmene kan betraktes som en smart og effektiv «modifikasjon» av en algoritme som ble oppfunnet i 1988 av MATSUMOTO og I MAI (Tsutomu Matsumoto og Hideki Imai, «Public quadratic polynomial-tuples for efficient signature-verification and message-encryption», Advances In Cryptology, Eurocrvpt ' 88 (Christoph G. Gunther, ed.), Lecture Notes in Computer Science, Vol. 330, Springer-Verlag, 1988, s. 419-453). Denne publikasjonen beskriver et asymmetrisk nøklingssystem med offentlig nøkkel og en hemmelig nøkkel, hvor kompleksiteten består i transformasjon av (m<2>n<3>) for offentlig nøkkel og (mn)<2>(m+logn) for hemmelig nøkkel.

Algoritmen oppfunnet av MATSUMOTO og IMAI ble knekket i 1995 av Jacques PATARIN, publisert ved CRYPTO'95-kongressen, "Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt '88", Springer-Verlag, s. 248-261. Det ble her tatt utgangspunkt i et nytt sikkert nøklingssystem med offentlig/hemmelig nøkkel fra MATSUMOTO og IMAI. Det ble beskrevet svakheter i systemet, og hva som skjer dersom systemet blir utsatt for angrep.

På grunn av dette angår foreliggende oppfinnelse en fremgangsmåte for asymmetrisk kryptografisk kommunikasjon. I følge foreliggende oppfinnelse er det tilveiebrakt en asymmetrisk kryptografisk kommunikasjonsprosess slik som definert i det vedføyde patentkrav 1, og i følge et annet aspekt ved oppfinnelsen er det tilveiebrakt et bærbart objekt som omfatter informasjonsprosesseringsanordninger og lagringsanordninger, og det bærbare objektet i følge oppfinnelsen defineres i det vedføyde patentkrav 12. Fordelaktige utførelsesformer av fremgangsmåten i følge oppfinnelsen fremgår av de uselvstendige patentkravene 2-11.

I fremgangsmåten for asymmetrisk kryptgrafisk kommunikasjon etableres en korrespondanse mellom en første verdi (x) representert av n elementer (xi,...,xn) i en ring (A) og en andre verdi (y) representert av m elementer (yi ym) i denne ringen, hvor n og m er heltall som er større enn eller lik 2, karakterisert ved at: - denne korrespondansen er definert ved flervariable offentlige polynomer (Pj) på A<n+m+k->> A, med lav total grad, slik at det er likninger av typen Pi(xi xn; yi ym; ^....z,*) = 0 hvor (zi,...,zk) er mulige mellomliggende variabler og k er et heltall;

- ihvertfall størsteparten av polynomene (Pi) er ikke på formen

Tj(yi ym) = Sj(xi,...,xn), hvor Sj-ene ville være polynomer med total grad 2 og Tj-ene ville være polynomer med total grad 1.

Begrepet «en verdi x» som skal transformeres i henhold til fremgangsmåten ifølge oppfinnelsen angir, etter hva som passer, enten en melding (for eksempel når fremgangsmåten anvendes for koding) eller mer generelt en størrelse som verifikasjon skal utføres på grunnlag av (for eksempel når fremgangsmåten anvendes til signaturverifikasjon eller autentifikasjon).

Begrepet «lav grad» som er nevnt nedenfor må forstås å angi en grad som er mindre enn eller lik 6, fortrinnsvis mindre enn eller lik 4, men samtidig større enn eller lik 2.

Andre detaljer og fordeler med oppfinnelsen vil bli klare fra den følgende beskrivelsen av visse foretrukne, men ikke begrensende, utførelsesformer med henvisning til de vedføyde tegningene, hvor: Figur 1 er et diagram som illustrerer sammenkjedingen av transfor-masjonene som anvendes for å prosessere en melding, i henhold til en første variant av fremgangsmåten ifølge oppfinnelsen, som anvendes ved koding; og Figur 2 illustrerer et eksempel på et kodings/dekodings-system som anvender den kryptogråfiske kommunikasjonsprosessen ifølge oppfinnelsen.

2. - «Dragon«- algoritmen

2. 1 Det grunnleggende begrepet «Dragoner»

Navnet «Dragoner» er blitt gitt til en første familie av algoritmer basert på oppfinnelsen. Den grunnleggende forestillingen som skiller de to familiene av algoritmer, «Dragon» og «Matsumoto-lmai», skal nå presenteres. Deretter, i de påfølgende avsnittene, vil det bli gitt visse spesielt foretrukne eksempler på «Dragoner». Til slutt vil en annen familie av algoritmer som er basert på oppfinnelsen, «Kjeder» bli beskrevet.

For Matsumo - Imai

Den offentlige formen eksisterer i form av n flervariable polynomer i et endelig felt K, som gir en avbildningsverdi y som utgjøres av et mangfold av elementære avbildningsverdier yi, ..., yn som funksjon av en verdi x som utgjøres av et mangfold av elementære verdier xi, ..., xn på formen :

yi = Pi(xi xn)

y2<=> P2(X1 <X>„)

yn<=> Pn(Xi, ...,Xn)

hvor Pi, P2,...,Pn er polynomer av K[xi xn], dvs. polynomer på K<n->> K, idet disse polynomene har total grad 2.

For Dragonene

Den offentlige formen eksisterer i form av X flervariable polynomer i et felt K (eller en ring), hvor variablene yi, y2 ym og xi, x2l...,xn i K inngår på formen :

Pi(xi xn, yi,<y>2,...<y>m) <=> 0

P2(xi xn, yi,y2,-ym) <=> 0

Px(xi xn, yi,y2....ym) <=> 0

hvor Pi, P2,.., Px, er polynomer på K<n> x Km -> K, med lav total grad (for eksempel 2).

Den fundamentale forskjellen mellom Dragon- og MATSUMOTO-IMAI-algoritmene ligger således i det faktum at, på den offentlige formen, er variablene Xj og yj blitt «blandet».

2. 2 - Første eksempel: den «Lille Dragon».

Til å begynne med vil nå et første, nokså enkelt, eksempel på en «Dragon»-algoritme bli presentert. Dette eksempelet illustrerer tydelig konseptet med Dragon-algoritmer, men denne algoritmen er uheldigvis ikke veldig kryptografisk robust, som angitt av forfatteren i artikkelen «Asymmetric Cryptography with a hidden Momomial» (LNCS 1109, Crypto '96, Springer, sidene 45 til 60). Deretter vil det i avsnittene 2.3, 2.4, 2.5 og 2.6 bli vist andre eksempler på Dragon-algoritmer hvor det til nå ikke er kjent noen generell angrepsmåte.

I dette tilfellet er X = m = n, og K er et lite endelig felt (for eksempel K = F2, feltet med to elementer). Antallet elementer i K betegnes q = IKI.

Dersom x = (xi,...,xn) er en verdi som i dette eksempelet utgjøres av en ukodet melding, og y = (yi yn) er den tilhørende kodete meldingen, kan overgangen fra x-i,...,xn til yi,...,yn beregnes som vist i figur 1 :

1) En første hemmelig affin bijektiv transformasjon s anvendes på

x = (xi xn) for således å oppnå en avbildning a = s(x) = (ai an).

2) En offentlig eller hemmelig transformasjon f anvendes på (a) og resulterer i en avbildning b = f { a) = aq"+ qr~}, hvor 8 og cp er offentlige eller hemmelige heltall slik at h = q<e> +q<cp> -1 er primisk med hensyn på q<n> -1, og hvor en kan øke potensen til h i en representant for feltet (vanligvis betegnet Fqn) med q<n>

elementer.

3) Til slutt transformeres b = (bi,...b„) til y = (yi,...yn) ved å anvende en andre hemmelig affin bijektiv transformasjon t på b slik at y = t(b).

Idet alle disse operasjonene er invertible, er det også mulig å beregne (xi,...x„) fra (yi,...,yn) dersom de hemmelige t og s er kjent, b = ah vil for eksempel bli invertert ved a = b<h>, hvor h' er et heltall slik at h.h' = 1 modulo q<n->1, hvor (.) er symbolet for multiplikasjon.

Dessuten, siden b = a/<*>"'"<1>, har en at b. a = a""<*>"', og derfor at det i en basis hvor a = (ai,...,a„) og b = (bL.-.bn), er n likninger på formen :

Det er derfor mulig, ved å uttrykke bj-ene som funksjon av yrene, og ar ene som funksjon av Xj-ene, å utlede at det er n likninger på formen :

det vil si, n likninger på formen :

Pi(xi, ...,xn, yi,.. yn) = 0, i = 1...n, hvor Pi er et polynom på K<2n->> K med total grad 2.

Disse n likningene Pj er gjort offentlige. De utgjør den offentlige nøkkelen.

På følgende måte kan derfor i praksis hvem som helst anvende dem for å kode en melding, det vil si å beregne yi,...,yn fra Xl...^, uten å kjenne til noen hemmelige nøkler. Ved å erstatte xi,...,xn med deres verdier og sette inn disse verdiene i likningene (2), oppnås n likninger med grad 1 for yrene

Alle løsningene av disse n likningene kan enkelt finnes ved Gauss-eliminasjon. Dersom a * 0 (hvilket alltid er tilfelle unntatt for enkelte x),

eksisterer det kun én løsning for b av b. a = al, 0*' i*, og det er derfor bare én løsning etter Gauss-eliminasjon : dette vil være den kodede meldingen (yi,...,yn) som skal sendes.

Den lille Dragon ved signatur.

Det er enkelt å anvende Lille Dragon algoritmen til signatur: dersom for eksempel yi,...,yn enten er meldingen som skal signeres eller et «hakk (hash)» av meldingen som skal signeres (det vil si resultatet av en spredningsfunksjon som er anvendt på meldingen), eller en offentlig funksjon av meldingen som skal signeres, vil Xi,...,xn være signaturen.

Signaturen verifiseres ved å verifisere at

dvs., ved å sjekke at alle de offentlige likningene (2) er tilfredsstilt.

2. 3 Mer generelle eksempler på Dragoner, med en «monom»- transformasion.

I dette tilfellet er X - m = n, og K er et lite endelig felt (for eksempel K = F2, feltet med to elementer). Antallet elementer i K betegnes q = IKI.

Dersom x = (xi,...,xn) er en verdi som i dette tilfellet utgjøres av en ukodet melding, og y = (yi y„) er den tilhørende kodete meldingen, kan overgangen fra xi x„ til yi,...,yn beregnes som følger, dersom en kjenner den hemmelige nøkkelen (fremgangsmåten for å beregne den fra x uten de hemmelige nøklene vil bli vist senere):

1) En første hemmelig affin bijektiv transformasjon s anvendes på

x = (xi,...,xn) for således å oppnå en avbildning a = s(x) = (ai an).

2) En offentlig eller hemmelig transformasjon f anvendes på (a) og resulterer en avbildning b = f(a) slik at: aA( q<e> + q*).M(b) = a<A>( q^ + q^). N(b), hvor 0 , cp, £ og 4 er offentlige eller hemmelige heltall slik at h = q<e> + q* - q; - q<4> er primisk med hensyn på q<n> -1, og hvor en kan øke potensen i en representant for feltet (vanligvis betegnet Fqn) med q" elementer, og hvor M og N er hemmelige eller offentlige affine funksjoner, (m og n er hemmelige a priori, men dersom de er offentlige må de velges med omhu for å unngå visse angrep.) Symbolet (<A>) betegner potensfunksjonen.

Hvordan beregnes b på grunnlag av a? Det vil nå bli vist at dette alltid er mulig ved å anvende en generell fremgangsmåte, men at det for visse spesifikke funksjoner M og N kan finnes raskere fremgangsmåter enn den generelle fremgangsmåten som nå vil bli presentert.

Dersom likning (1) uttrykkes ved komponentene (ai,...,a„) og (bi,...,b„) i a og b (c. til d. i en basis for Fqn), oppnås n likninger på følgende form :

hvor Yyk og er koeffisienter i K. Dette er på grunn av det faktum at funksjonene som assosierer x<A>(q<e>) med x, og som assosierer xA(q<p) med x er lineære funksjoner i Fqn, funksjonene som assosierer x<A>(q<e> + q^) med x, og som assosierer x<A>(q^ + q^) med x er derfor gitt i en basis av polynomer med total grad to.

Deretter, når a er gitt, oppnås n likninger av grad 1 i verdiene bj fra de n likningene (2). Det er derfor enkelt å finne løsningene av disse likningene ved Gauss-eliminasjon. Det er antatt at det finnes minst én løsning slik at M(b) * 0 eller N(b) * 0. Dersom det finnes mer enn én løsning velges en av disse tilfeldig. 3) Til slutt transformeres b = bn) til y = (yi,...,yn) ved å anvende en andre hemmelig affin bijektiv transformasjon t på b slik at y = t(b).

Idet alle disse operasjonene er invertible er det derfor også mulig å beregne (xi,...xn) fra (yi,...,yn) dersom de hemmelige nøklene t og s er kjent. Dersom for eksempel M(b) * 0, vil a finnes fra b ved : a = (N(b)/M(b))<h>, hvor h' er den inverse av :

h = qe + q* - - q^ modulo q"-1.

Offentlig beregning av (yi,—,yn) på grunnlag av (xi,...,xn):

De n likningene (2) vil bli transformert til et system av n likninger på følgende form:

dvs. n likninger Pi^ xn, yi,...,yn) = 0, i=1...n, hvor Pj er et polynom på K<2n> til K med total grad 3.

Disse n likningene (3) vil være offentlige. De utgjør den offentlige nøkkelen. Ved å anvende disse likningene (3), er det ved Gauss-eliminasjon mulig å beregne alle løsningene (yi,...,yn) på grunnlag av ^.....Xn) uten kjennskap til hemmelige nøkler.

Disse n likningene (3) oppnås fra de n likningene (2) i følgende to trinn : Trinn 1 : Variablene bi erstattes med deres affine uttrykk i variablene yj og variablene ax erstattes med deres affine uttrykk i variablene Xj.

Trinn 2 : Deretter anvendes en hemmelig affin bijektiv transformasjon på disse likningene.

2. 4 Et eksempel på signatur med m^ n.

Følgende er et eksempel som kan anvendes i signatur, med m * n.

La som vanlig y = (yi,...,ym) betegne et hakk av meldingen som skal signeres (eller meldingen som skal signeres).

La Qi,...,Qn og Q'^..^,, være 2n hemmelige flervariable polynomer med total grad 2 på K<n> -> K.

La b = t"<1>(y), hvor t er en hemmelig affin bijeksjon av Km -> Km; b =

(bi,b2,...,bm).

La B betegne elementet i K<n> med komponentene :

B <=> (Qi(bi,b2 bm), Q2(bi,b2 bm),... Qn(bi,b2 bm)).

Og la B' betegne elementet i Kn med komponentene :

B' = (Q'i(bi,b2 bm), Q'2(bi,b2 bm),... Q'n(bi,b2,...,bm)).

En kan betrakte B og B' som å representere (i en basis) to elementer i feltet Fqn.

I dette feltet, la a være elementet slik at:

a er representert i en basis ved a = (ai an).

La til slutt x = s(a), hvor s er en hemmelig affin bijeksjon av K<n->>K<n>.

x = (xi,..,,xn) i en basis.

Ved å uttrykke likning (3) i en basis, og ved å uttrykke likningene ved variablene Xj og y,, oppnås n likninger med total grad 4 i variablene x1 xn, yi ym.

Disse n likningene vil være offentlige og (x, xn) vil være en gyldig signatur av (y1 ym) hvis og bare hvis alle disse n likningene verifiseres.

For å beregne en signatur med de hemmelige nøklene trenger en kun å beregne b, så B og B', deretter a fra (3) og til slutt x ved å anvende x = s(a). 2. 5 Mer generelle eksempler på dragoner, med en «ikke- monom polynom»-transformasjon.

De samme betegnelsene som før vil bli beholdt. Ved koding betegner x fortsatt den ukodede meldingen, og y betegner den kodede meldingen (ved signatur er x signaturen og y er en offentlig transformasjon av meldingen som skal signeres, for eksempel er y Hash(M), hvor Hash er en spredningsfunksjon).

La fortsatt a = s(x) betegne transformasjonen av x med en hemmelig affin bijeksjon s, og la b betegne transformasjonen av y med en hemmelig transformasjon (y = t(b)). a betraktes som et element i feltet Ki med q<n >elementer (K1 = Fqn) og b betraktes som et element i feltet K2 med q<m >elementer (K2 = Fqm).

Et eksempel hvor overgangen fra a til b er noe mer generell enn tidligere vil nå bli presentert.

La k og k' være to heltall, og la Ni, 1 <= i <= k, og N'j, 1 <= i <=k' være hemmelige affine funksjoner fra K2 til Ki (som tidligere betyr «affine» at disse funksjonene er affine når K2 og Ki betraktes som vektorielle rom i feltet K med q elementer); dessuten betyr symbolet (<=) «mindre enn eller lik».

La til slutt, for ethvert element a i Ki og ethvert element b i K2,

hvor, i den første summen Z i går fra 1 til k, og i den andre summen Z fra 1 til k'.

La d være dette polynomets grad i a. Det finnes kjente algoritmer for å finne løsningene for a i likningen f(a,b) = 0 dersom ikke d er for stor (for eksempel d <= 8000). f(a,b) ble dessuten konstruert slik for å uttrykkes i en basis i form av polynomlikninger med total grad 3 (total grad 2 i variablene a-,, og 1 i variablene bj). Som tidligere vil likningene bli skrevet ved å substituere for variablene a; deres affine uttrykk i variablene Xj og ved å substituere for variablene bj deres affine uttrykk i variablene yj. Deretter utføres en hemmelig affin bijektiv transformasjon u på likningssystemet som er oppnådd og systemet som således oppnås gjøres offentlig : dette er den offentlige nøkkelen. Denne offentlige nøkkelen utgjøres derfor av likninger med total grad 3 (total grad 2 i variablene Xj, og 1 i variablene yj). På grunnlag av disse offentlige likningene er det med Gauss-eliminasjon mulig å beregne løsningene y, som svarer til en gitt x. Den inverse operasjonen derimot (å beregne x fra y), krever kjennskap til en hemmelig nøkkel.

2. 6 «Ufullstendige Dragoner».

I alle eksemplene som er gitt på «Dragon»-algoritmer for koding er, dersom overflødige data innføres i meldingen x, algoritmen for dette offentlig, det er derfor mulig å ikke gjøre offentlige alle likningene som var offentlige likninger, dvs. å holde et lite antall av disse hemmelige. Dette kan i praksis øke algoritmens robusthet. Den korrekte verdien for x vil da finnes på grunnlag av de offentlige overfødige dataene.

Tilsvarende er det ved signatur mulig å ikke gjøre offentlige alle likningene som tidligere ble betegnet offentlige likninger: verifikasjonen av signaturen vil da utføres med færre likninger.

Det er mulig å forestille seg andre eksempler på «Dragon»-algoritmer. Det er imidlertid veldig viktig å være klar over det faktum at visse varianter ikke er kryptografisk robuste : i artikkelen «Asymmetric Chryptography with a hidden Monmial» (LNCS 1109 Crypto '96, Springer, sidene 45 til 60), presenterte forfatteren noen angrep på visse lite robuste varianter.

3. - «KJEDE»- ALGORITMER

3. 1 - Den grunnleggende ideen med «Kjeder»

Den grunnleggende ideen med «kjeder», sammenliknet med MATSUMOTO-IMAI, er å innføre mellomliggende variabler Z\, 1 <= i <= k, dvs. å ha offentlige polynomer Pj som ikke bare avhenger av de vanlige variablene x, og yi (hvor Xi-ene representerer meldinger som skal kodes og yj-ene representerer den kodede meldingen ved koding, eller hvor xrene representerer signaturen av yi-ene ved signatur) men også av de mellomliggende variablene z,.

3. 2 - Første eksempel: «Små kjeder».

Til å begynne med vil det bli presentert noen første, nokså enkle, eksempler på «Kjede-algoritmer». Disse eksemplene illustrerer klart konseptet med Kjede-algoritmer, men disse første eksemplene er dessverre ikke særlig kryptografisk robuste. Det er i praksis mulig å generalisere visse angrep fra artikkelen «Asymmetric Chryptography with a Hidden Monomial» (LNCS 1109 Crypto "96, Springer, sidene 45 til 60) til disse eksemplene. Deretter, i seksjon 3.5, vil det bli gitt andre eksempler på Kjede-algoritmer som det hittil ikke er kjent generelle angrepsmåter på.

La for eksempel a, b, c og d være fire elementer i feltet med q<n >elementer og la fire heltall 0, cp, a og p være slik at:

derfor er b = ah hvor h = qa + qa+<e> + q<p> + q<p+<p.> Det er antatt at 0, cp, a og p er valgt slik at h er primisk med hensyn på q<n> -1.

Anta deretter at x = s(a) og y = t(b), hvor s og t er hemmelige affine bijektive funksjoner. La videre z = u(c) og z' = v(d), hvor u og v er hemmelige affine funksjoner.

Fra (1) har en at det finnes n relasjoner på formen :

Likeledes har en fra (2) at det finnes n relasjoner på formen :

Likeledes har en fra (3) at det finnes n relasjoner på formen :

Anta deretter at de 3 x n likningene (1<1>), (2') og (3') er offentlige. Derfor vil, dersom x er meldingen som skal kodes, Zi-ene bli oppnådd fra (1'), zVene bli oppnådd fra (2'), og deretter yrene bli oppnådd fra (3<1>). Det er således mulig å beregne den kodede meldingen y på grunnlag av x samt fra de offentlige polynomene.

På den annen side, dersom y er kjent men x er ukjent, kan det se ut til at det ikke alltid er mulig å finne tilbake x fra y. I praksis er det fra (3') kun mulig å gå tilbake til n likninger for de 2 x n variablene Z\ ,og z'\, og Zi-ene og z'j-ene forblir derfor ukjente.

På den annen side, dersom de hemmelige nøklene s og t er kjent, er det mulig å beregne b = t"<1>(y) fra y, deretter a = b<h>, hvor h' er den inverse av h modulo q<n> -1, og til slutt x = s(a). Det er således mulig, med den hemmelige nøkkelen, å dekode meldingene.

3. 3. - Andre eksempel: små kieder med Dragon.

Den samme notasjonen som i den forrige seksjonen vil bli beholdt, men det vil nå bli antatt at:

hvor 9, cp, 8", cp', a, (3 og y er heltall. Derfor er likeledes b = aM for spesifikk \ i og 8, cp, a, 8', cp', a, (3 og y vil bli valgt slik at \ i er primisk med hensyn på q<n> -1. Denne algoritmen vil virke på eksakt samme måte, men denne gangen er de offentlige likningene (1') på formen : og de offentlige likningene (2') er på formen :

Dersom x er meldingen som skal kodes, vil Zj-ene bli oppnådd fra (1') ved Gauss-eliminasjon og yrene vil bli oppnådd fra (3').

3. 4 - Anvendelse av kieder for signatur.

Eksemplene i seksjonene 3.2 og 3.3 som er gitt for koding kan også anvendes for signatur. I dette tilfellet representerer x signaturen som er assosiert med y, og signaturverifikasjonen består i å verifisere hvorvidt det faktisk eksisterer variabeler Zj og z'j som tilfredsstiller (1'), (2') og (3').

3. 5 - Mer generelle kjeder.

I en offentlig nøkkel, i eksemplene i seksjonene 3.2 og 3.3, ble de mellomliggende variablene z og z' oppnådd fra x, og y ble deretter oppnådd fra z og z'. Det er mulig å forestille seg lengre kjeder.

Det er for eksempel mulig, på grunnlag av Xj-ene, å oppnå variabler z,. Det er deretter mulig, på grunnlag av variablene Xj og Z\, å oppnå variabler zV Deretter ville, fra variablene Xj, z\ og z'\, variablene z" bli oppnådd. Til slutt ville y bli oppnådd fra variablene Xj, Zj, z'\ og z",..,.

Et eksempel på denne mer generelle typen kjede, som det ikke er kjent noen angrepsmetode for, vil nå bli presentert.

Notasjon.

x er den ukodede teksten,

y er den kodede teksten,

s og t er to hemmelige affine funksjoner,

b = t(y),

a = s(x),

k er et heltall (dette er antallet «ledd» i kjeden),

a, b, Ll L2,...Lk, Ml M2 Mk er elementer i F2<n>,

Si,...,Sk, ti,...tk er 2k hemmelige affine bijeksjoner,

for enhver indeks i slik at 1 <= i <= k : lj = Sj(Li),

og mi = ti(Mj).

Kommentar

x, y, li,...,lk og mi,...,mk er verdiene som vil opptre i de offentlige likningene og a, b, Li, L2j...,Lk og Mi,...,Mk er verdiene som er aksessible med de hemmelige nøklene.

For alle indekser i, 1 <= i <= k finnes det to eksponenter hj og h', slik at : Li = a<h>j og Mi = ah'j (ytterligere detaljer om hi og h'i er gitt nedenfor), og det finnes en eksponent h slik at: b = ah.

Beregningen av de hemmelige nøklene vil således bli enkel:

1. Beregn b = t(y),

2. Beregn a = b<h> hvor hh' = 1 modulo 2n -1,

3. Beregn til slutt x = s"<1>(a).

De offentlige likningene vil nå bli beskrevet. Det finnes to typer av disse : det er «ledd»-typen likninger (som det er 2k.n stykker av), som gjør det mulig å gå fra x til h eller fra x til itm eller fra li til lj+i eller fra nrij til mj+i, og det er de n endelige offentlige likningene som gjør det mulig å gå fra (lk,mk) til y. «Ledd»-typen likninger.

Betrakt som et eksempel måten en går fra x til U \ det er praktisk talt det samme for de andre «leddene», dvs. for å gå fra li til li+i eller fra x til mi eller fra mj til mi+i, 1 <= i <= k-1.

Det er fire hemmelige heltall, som betegnes a, p, y og 8, slik at:

a. p, y og 5 er videre valgt slik at:

SFN(2<Y> - 2a, 2" -1) = 1 og SFN(28-2P, 2n -1) = 1 (hvilket gjør det mulig å ha bijektive transformasjoner). Det minnes om at SFN betyr «Største fellesnevner».

Når (C1) uttrykkes i en basis med komponentene Xi av variabelen x og variabelene 11, i av variabelen 11 oppnås n likninger på formen :

Disse n likningene (C2) er offentlige (eller, mer presist, en lineær bijektiv transformasjon av disse likningene er gjort offentlig).

Fra disse likningene (C2) er det mulig å, uten å kjenne hemmelige nøkler, å beregne h fra x ved Gauss-eliminasjon.

Likeledes er det mulig å beregne l2 fra l1f deretter l3 fra l2 osv., opp til lk fra ln, og det er derfor mulig å beregne lk fra x. Likeledes er det mulig å beregne mk fra x. Det er derfor mulig å beregne lk og mk fra x ved hjelp av de 2k.n offentlige likningene.

De endelige offentlige likningene.

De n «endelige» offentlige likningene vil da gjøre det mulig å beregne y fra mk og lk. (I dette tilfellet er beregningen «enveis», hvilket betyr at det uten kjennskap til hemmelige nøkler ikke er mulig å vite hvordan å komme tilbake til mk og lk fra y). Her er to typiske eksempler på mulige endelige likninger. hvor a', P', a" og p" er hemmelige heltall.

hvor 0 og cp er hemmelige heltall.

Denne likningen ((C3) eller (C4)) uttrykkes i en basis med variablene yj, mk,j og lk,j. Det oppnås således n likninger. En lineær og bijektiv transformasjon av disse n likningene gjøres offentlig, hvilket gjør det mulig å beregne y fra lk og mk (ved Gauss-eliminasjon).

Det vil således være mulig, på grunnlag av offentlige likninger, å beregne y på grunnlag av x, som det var ønsket. 4. - FREMGANGSMÅTE FOR A REDUSERE STØRRELSEN PÅ DE OFFENTLIGE NØKLENE.

De hemmelige affine funksjonene s og t som inngår i Dragon- og kjede-algoritmene er koeffisienter med verdier i den samme ringen A som variablene som inngår. Det er imidlertid av og til fordelaktig å begrense seg til koeffisienter i en underring A' av A, siden de offentlige polynomene i det tilfellet selv vil kunne ha koeffisienter i en underring A" av A, hvilket gjør det mulig å redusere antallet bits som er nødvendig for å beskrive disse offentlige polynomene. Denne teknikken er spesielt hensiktsmessig i eksemplene gitt ovenfor.

5. - EN MÅTE Å UNNGÅ Å LAGRE POLYNOMENE P,

I et chip-kort som kan beregne verdiene (y) fra (x), og muligens (x) fra (y), er det ikke alltid nødvendig at alle de offentlige polynomene Pj lagres. I praksis, siden disse polynomene har en lav total grad, kan kortet levere verdiene (x), og (y) som hører til (x), som det fra utsiden er mulig å beregne de offentlige polynomene Pj på grunnlag av. Mer generelt kan det levere verdier som gjør det mulig å beregne de offentlige polynomene Pj, hvor verdiene kan være signert, eller hvor polynomene som skal finnes kan være signert, og hvor signaturen (og ikke alle de offentlige polynomene) ville være lagret i kortet.

6. - KODINGS-/ DEKODINGSSYSTEM SOM ANVENDER FREMGANGSMÅTEN IFØLGE OPPFINNELSEN

Figur 2 illustrerer skjematisk et eksempel på et kjent kodings-/dekodingssystem som anvender den kryptografiske

kommunikasjonsprosessen som er beskrevet ovenfor.

Anta at det er to enheter A og B som er forbundet til det samme kommunikasjonsnettverket, og som hver har sin respektive anordning for sending/mottak 1,2. Denne anordningen inkluderer beregningsanordninger, for eksempel en datamaskin som er konstruert for å utføre koding/dekoding av meldinger, og lagringsanordninger. Ihvertfall deler av disse beregnings- eller lagringsanordningene kan være plassert i et bærbart objekt som omfatter en mikroprosessor eller mikro-tvunnede (micro wired) logiske kretser som definerer områder hvor tilgangen er regulert, og som derfor kan inneholde hemmelig informasjon så som kryptografiske nøkler (se for eksempel det bærbare objektet som er beskrevet i US patent nr. 4 211 919).

Hver anordning omfatter en algoritme F som beskrevet ovenfor, mer spesifikt i form av et program, så vel som den inverse algoritmen F"<1>. De to anordningene er forbundet med hverandre ved hjelp av en kommunikasjonslinje 3.

Begge enhetene, henholdsvis A og B, har et par av nøkler: en offentlig nøkkel CpA og CpB, og en hemmelig nøkkel CsA og Cs<B> innbyrdes forbundet med den tilhørende offentlige nøkkelen Cp<A> eller CpB.

Enhet A sender B sin offentlige nøkkel Cp<A> og muligens en signatur av denne offentlige nøkkelen, og B sender A sin offentlige nøkkel CpB og muligens en signatur av denne offentlige nøkkelen. Når A har mottatt den offentlige nøkkelen CpB, vil den anvende den, sammen med den kryptografiske algoritmen F, for å kode en melding M som den ønsker å sende til B, og en melding M". Denne meldingen, når den er mottatt av B, dekodes ved å anvende den kryptografiske algoritmen F"<1> og den hemmelige nøkkelen Cs<B>.

Claims (12)

1. Asymmetrisk kryptografisk kommunikasjonsprosess som etablerer en korrespondanse mellom en første verdi (x) representert av n elementer (xi...,x„) i en ring (A) og en andre verdi (Y) representert av m elementer (yi...,ym) i denne ringen, hvor n og m er heltall som er større enn eller lik 2, karakterisert ved at: - nevnte korrespondanse defineres ved flervariable offentlige polynomer (P,) på A<n+m+k->> A, med en total grad som er mindre enn eller lik 6, slik at det er likninger av typen P^ xn; yi ym; zi,...zk) = 0 hvor (zi Zr) er mulige mellomliggende variabler og k er et heltall; - idet i det minste noen av polynomene (Pj) er slik at relasjonen Tj(yi,...,ym) = Sj(xi xn) ikke verifiseres, hvor Sj-ene ville være polynomer med total grad 2 og Tj-ene ville være polynomer med total grad 1.

2. Prosess ifølge krav 1, karakterisert ved at visse polynomer (Pj) er slik at relasjonen T\( yi ym) = Sj(x-j xn) ikke verifiseres, hvor Sj-ene ville være polynomer med total grad mindre enn eller lik 6 og Tj-ene ville være polynomer med total grad 1.

3. Prosess ifølge krav 1, karakterisert ved at de flervariable offentlige polynomene (Pj) er på formen Pj(xi,...,xn; yi ym;) = 0, idet visse polynomer er slik at det finnes et helt tall j mellom 1 og n, og et helt tall p mellom 1 og m, slik at nevnte polynomer (Pj) inneholder minst ett ikke-trivielt monom i Xj.yp.

4. Prosess ifølge krav 3, karakterisert ved at nevnte korrespondanse mellom den første verdien (x) og den andre verdien (y) defineres som følger:

1) ved å anvende kjennskapet til to hemmelige affine transformasjoner s og t, hvor s er en affin transformasjon på A" -> An, dvs. bestemt ved n polynomer med total grad 1 i n variabler, og t er en affin transformasjon på Am -> Am, dvs. bestemt ved m polynomer med total grad 1 i m variabler, beregnes en funksjon y = F{x) på følgende måte: 1.1) den affine transformasjonen s anvendes på x slik at det oppnås en avbildning : a = s(x) 1.2) en transformasjon f anvendes på avbildningen (a) og resulterer i en avbildning b slik at b - f(a), hvor: 1.2.1) dersom a = (ai, a2,.,ai,..,an) og b = (bi, b2l..(bj,..,bm), (hvor ai og bj er elementer i A), er det en korrespondanse definert ved flervariable offentlige polynomer (Vj) på An+m -> A som er ikke-trivielle, har lav total grad og som hver tilfredsstiller en likning av typen : Vj(ai, a2l..,ai,..,an; bi. b2,..,bj,..,bm) = 0 (I) idet visse polynomer (Vj) er slik at det finnes et helt tall j mellom 1 og n, og et helt tall p mellom 1 og m, slik at nevnte polynomer (Vj) inneholder minst ett ikke-trivielt monom i aj.bp; 1.2.2) transformasjonen f er også valgt slik at det finnes en algoritme som gjør det mulig, for mange avbildninger b, å beregne minst én avbildning (a) slik at: f(a) = b. 1.3) den affine transformasjonen t anvendes på avbildningen b, slik at t(b) = y oppnås;

2) på grunn av likningene (I) er det mulig, ved et variabelskifte, å vise eksistens av likningene (II) som definerer de nevnte flervariable polynomene (Pj): hvor noen av disse polynomene er offentlige.

5. Prosess ifølge krav 1, karakterisert ved at de flervariable polynomene (P,) omfatter definerte polynomer (Qj) på A<n+k> -> A på formen Qj(xi,...,x„; Zi zk;) <=> 0 og definerte polynomer (Rp) på A<m+k>> -+ A på formen Rj(yi,...,ym; z\ z'k ) = 0, hvor fa zk) og (z'i,...,z'k) er mellomliggende variabler, og j, p,k og k<*> er heltall.

6. Prosess ifølge krav 1, for å beregne en meldingssignatur hvor den andre verdien y = <yi ym) representerer meldingen som skal signeres eller en funksjon av meldingen som skal signeres, og hvor den første verdien x = (xi xn) representerer signaturen til meldingen, karakterisert ved at den omfatter verifikasjon av meldingssignaturen ved å verifisere at nevnte likninger for polynomene (Pj) faktisk er tilfredsstilt, det er underforstått at dersom variablene z-i,...,zk inngår i disse likningene er det nødvendig å verifisere hvorvidt det faktisk eksisterer variabler av denne typen (zi,...,zk) som vil tilfredsstille alle disse likningene.

7. Prosess ifølge krav 1, for å kode en melding hvor den første verdien x = (xi,...,xn) representerer meldingen som skal kodes, og hvor den andre verdien y = (yi,--,ym) representerer den kodede meldingen, karakterisert ved at den består av å anvende nevnte korrespondanse med den første verdien x for å oppnå, for noen av eller alle verdiene til x, en andre verdi y, ved å anvende et sett av offentlige nøkler som inkluderer nevnte flervariable offentlige polynomer (Pj).

8. Prosess ifølge krav 1, for utføring av asymmetrisk autentifikasjon ved en første person, betegnet en verifikator, av en annen person, betegnet en bevisfører, karakterisert ved at: - verifikatoren sender bevisføreren en verdi som utgjøres av den andre verdien (y); - bevisføreren returnerer en verdi til verifikatoren som utgjøres av den første verdien (x); - verifikatoren verifiserer at nevnte likninger i polynomene (Pj) faktisk er kompatible med de første (x)- og (y)- verdier, det er underforstått at dersom variablene Zi,...,zk inngår i disse likningene, er det snakk om å verifisere hvorvidt det faktisk eksisterer variabler av denne typen (zi zk) som vil tilfredsstille alle disse likningene.

9. Prosess ifølge krav 1, karakterisert ved at - korrespondansen inkluderer minst én affin transformasjon s som er definert ved en matrise som er sammensatt av koeffisienter med verdier i nevnte ring (A) - nevnte koeffisienter i matrisen har verdier i en underring (A') av (A) slik at nevnte flervariable offentlige polynomer (Pj) vil ha koeffisienter i en underring (A") av (A).

10. Fremgangsmåte ifølge krav 1, karakterisert ved at hvert monom av nevnte flervariable offentlige polynomer (Pj) inneholder minst én variabel yj, hvilket betyr at polynomenes (Pi) totale grad i variablene yj er 0 eller 1.

11. Fremgangsmåte ifølge krav 1, karakterisert ved at - A er et endelig felt K med et lite antall elementer som betegnes q = IKI; - m = n; - a og b representerer verdiene på to elementer i feltet Fq<n> med q<n> elementer; - transformasjonen f er en bijeksjon på formen f(a) = b = ah, hvor h er et offentlig eller hemmelig heltall og som er primisk med hensyn på q<n> -1.

12. Bærbart objekt som omfatter informasjonsprosesseringsanordninger og lagringsanordninger, og som er konstruert for å utføre en asymmetrisk kryptografisk kommunikasjon som etablerer en korrespondanse mellom en første verdi (x) representert ved n elementer (xi,...,xn) i en ring (A) og en andre verdi (y) representert ved m elementer (y^.., yj,..,ym) i denne ringen, idet n og m er heltall som er større enn eller lik 2, karakterisert ved at: - nevnte korrespondanse er definert ved flervariable offentlige polynomer (Pj) på A<n+m+k->> A, med en total grad som er mindre enn eller lik 6, slik at Pi(xi,...,xn; yi ym; z1(...zk) = 0 hvor (zi zk) er mulige mellomliggende variabler og k er et heltall; - i det minste noen av polynomene (Pj) er slik at relasjonen Tj(yi ym) = Sj(xi xm) ikke verifiseres, hvor Sj-ene ville være polynomer med total grad 2 og Tj-ene ville være polynomer med total grad 1; - nevnte lagringsanordninger lagrer ikke de flervariable offentlige polynomene (Pj); - hva angår beregningen av de flervariable offentlige polynomene (Pj), er det bærbare objektet konstruert for kun å levere dataene som gjør det mulig å beregne, fra utenfor det bærbare objektet, de flervariable offentlige polynomene (Pi), hvilke gjør det mulig å beregne den andre verdien (y) på grunnlag av den første verdien (x).