NO323723B1 - Fremgangsmate for a tilordne en numerisk signatur - Google Patents

Description

Oppfinnelsen gjelder en fremgangsmåte for å tilordne en numerisk signatur (c,d) til en informasjonsmengde M (som også gjerne kan kalles en melding), så vel som en måte å autentisere en slik signatur på.

Hensikten med numeriske signaturer er å bekrefte utstedelsen av et elektronisk dokument, og med numerisk signatur menes her en signatur i digitalt format. På tilsvarende måte som et papirmanuskript signeres, tilføyes en numerisk signatur til et elektronisk overført dokument for å garantere autentitet. Et eksempel som gir et praktisk aspekt er at en enhet (person, maskin) A i et sambandssystem ønsker å adressere en informasjonsmengde M til en tilsvarende enhet B. I en første fase av denne adressering eller overføring av informasjon frembringes en signatur hos enheten A etter at informasjonsmengden er konfigurert (meldingen er skrevet), deretter utføres flere matematiske trinn som er relatert til informasjonsmengden M som skal signeres , og for operander som like gjerne kan være hemmelige som offentlig tilgjengelige. De matematiske trinn i form av beregninger fører til generering av en numerisk enhet som man i dette tilfelle kan kalle signaturen. Mengden M så vel som signaturen overføres deretter elektronisk. I en andre fase, etter mottakingen av mengden M med tilhørende signatur utføres i enheten B (av mottakeren) tilsvarende matematiske trinn, og resultatet gir mulighet til å få bekreftet gyldigheten av den mottatte signatur. Det skal bemerkes at hensikten med signaturen er å sikre autentisering av informasjonsmengden M og ikke garantere at innholdet er riktig. Informasjonsmengden kan altså overføres enten i klar tekst eller kodet/kryptert ved hjelp av algoritmer som er fullstendig uavhengige av signaturmekanismen.

Generelt tillater en fremgangsmåte for signaturtilordning i et moderne sambandssystem både autentisering på sikker måte av identiteten av sendingen av en informasjonsmengde, og integriteten av innholdet i informasjonsmengden, ved at man får verifisert at denne mengde ikke har blitt endret i løpet av overføringen.

Ved tilordning av numeriske signaturer bygger sikkerheten på at det er særdeles vanskelig å arbeide seg tilbake gjennom bestemte matematiske sammenhenger. Selv om man tar i betraktning moderne datamaskiners enorme regnekraft er det likevel så å si umulig å finne løsningen i bestemte likninger uten å kjenne visse hemmeligholdte elementer i enkelte algoritmer.

I dag har man flere typer fremgangsmåter for slik tilordning av numeriske signaturer, og en første type er utviklet av Rivest, Shamir og Adelman og bygger på vanskeligheten i å faktorisere store heltall (se publikasjonen; "A method for obtaining digital signatures and public key cryptosystems" i Communications of the ACM, februar 1979, vol. 21, nr. 2, pp. 120-126, samt US patent 4 405 829 som bygger på dette litteratursted).

En andre type fremgangsmåte er utviklet av Taher El-Gamal og foreslår signaturalgoritmer som bygger på det diskrete logaritmeproblem som involverer diskret eksponentialdannelse (se publikasjonsen: "A Public Key Cryptosystem and a Signature Scheme base don Discrete Logarithms", IEEE Trans. On Innform. Theory, vol. IT-31, pp. 469-472, juli 1985.

Diskret eksponentialdannelse innbefatter bruk av tre argumenter, nemlig basis-eller grunntallet g, eksponenten x og modulus N, det vil si restleddet. Det diskrete logaritmeproblem innebærer, når man har det matematiske forhold Y=g<x> modulus N (hvilket betyr at Y er divisjonsresten når g<x> divideres med N), å finne x når man kjenner N, g og Y.

En fremgangsmåte av samme type, men enklere er foreslått av Schnorr og har ført til US 4 995 082. Fremgangsmåten skiller seg fra El-Gamals teori ved å gå ut på å redusere størrelsen av eksponenten i diskrete eksponentfunksjoner for å forsere frem beregninger. For dette genererer et element eller argument g en undergruppe av orden q, og med q angitt som for eksempel 160 b på digital form. Videre brukes en bestemt nøkkeltransformasjon (hache- eller spredefunksjon) ved beregningen av signaturen. Den numeriske signatur som på denne måte frembringes er derfor ikke plasskrevende.

Generelt kan diskrete eksponentfunksjoner være modulære eller i form av multiplikasjon av et heltall over en elliptisk kurve, idet den første bygger på bruken av heltall sammen med et valgt tall for et restledd som blir igjen ved divisjon, mens man i det andre tilfelle multipliserer et heltall langs en elliptisk kurve, idet dette tilsvarer den modulære eksponentdannelse, men defineres i en gruppe som er angitt additivt og ikke multiplikativt.

I en rekke anvendelser bør den numeriske signatur så vel som dens bekreftelse kunne håndteres i sanntid. Visse fremgangsmåter, så som El-Gamals krever i så fall kraftige maskiner, siden det trengs stor regnekraft for håndtering av algoritmene. For å unngå et slikt behov muliggjør optimalisering av algoritmene en reduksjon av regnearbeidet, selv om man oppnår samme eller i alle fall tilnærmet samme sikkerhet.

Den løsning som bygger på diskret eksponentdannelse er den mest brukte i dag innenfor kryptering, og man har også kommet med visse forbedringer i algoritmene for å øke beregningshastigheten, med bibehold av maksimal sikkerhet. I dette perspektiv er det viktig å kunne redusere størrelsen (lengden av digital sekvens, målt i b) av eksponenten, siden beregningstiden for den modulære eksponentdannelse er pro-porsjonal med størrelsen.

I de algoritmer som i dag er kjent er kardinalparameteren i denne funksjons-gruppe valgt av størrelsen N (restleddet eller modulus). Siden algoritmens sikkerhet er basert på diskret eksponentdannelse må det være umulig å finne løsningen. Denne sikkerhet innbefatter bestemte begrensninger i valget av denne størrelse N. Ved modulær eksponentdannelse har man ifølge den kjente teknikk og for ikke å redusere sikkerheten bare kunne foreslå to muligheter for valg av N. I denne første mulighet bestemmes N som et produkt av to primtall. Ifølge El-Gamal foreslås å velge N slik at (N-l)/2 er et primtall, mens divisor i mente er (N-l).

Den andre mulighet gjelder algoritmer som bygger på diskret eksponentdannelse og hvor undergruppe må være kjent så vel som dennes kardinalparameter, idet denne parameter er en divisor N-l dersom N er et primtall eller en divisor ut fra antallet punkter på kurven i det tilfelle man har en elliptisk kurve. Ifølge Schnorr foreslås å velge q som kardinalparameter i undergruppen og slik at q deler (N-l).

I og med oppfinnelsen unngås disse ulemper ved at man foreslår en fremgangsmåte som både kan redusere kompleksiteten av beregningene og tillater at man kan arbeide i sanntid med en mer ordinær datamaskin, for eksempel av typen PC. De begrensninger som er angitt ovenfor elimineres også ved at valget av størrelsen N ikke lenger er begrenset til de to gitte muligheter og hvor beregningen av en rekke punkter på en elliptisk kurve ikke lenger er nødvendig.

Således er det skaffet tilveie en fremgangsmåte for å tilordne en numerisk signatur (c, d) til en informasjonsmengde (M) som skal overføres, idet man først definerer et restledd (modulus N), et grunntall (g), en offentlig nøkkel (Y) og en privat nøkkel (x), kjennetegnet ved at størrelsene N, g, Y og x står i forhold til hverandre på denne måte:

Y=g<x> (modulus N),

- nøkkeltransformasjon ved at man bestemmer en spredefunksjon H slik at størrelsen av resultatet blir S (b),

- valg av et antall r på T siffere (b), idet T > 2S,

- beregning av en størrelse u ut fra likningen u = gr • Y<z>, idet Z = 2S,

- nøkkeltransformasjon ved hjelp av spredefunksjonen H, av kjeding av informasjonsmengden M og størrelsen u, idet det tall som kommer frem som et resultat brukes som signaturen c, og

- beregning av signaturen størrelse d ut fra sammenhengen d = r + cx.

Således er det også skaffet tilveie en fremgangsmåte for autentisering av en numerisk signatur (c, d) som er tilordnet en informasjonsmengde (m), idet signaturen er frembrakt ved en fremgangsmåte kjennetegnet ved at man går ut fra at den allment tilgjengelige nøkkel Y, restleddet N, grunntallet g og spredefunksjonen H og derved størrelsen S er kjent:

- beregning av u ut fra forholdet u = gdy(z-c), idet Z = 2S,

- nøkkeltransformasjon med spredefunksjonen H av kjededannelsen av M og u, og - bekreftelse av at den oppnådde verdi er lik signaturen c i det tilfelle denne er autentisk.

Ifølge en tilleggskarakteristikk som gir ytterligere mulighet for å redusere beregningstiden utføres nøkkeltransformasjon av informasjonsmengden M med en funksjon h| før spredefunksjonen H brukes, hvoretter kjeding med u foretas, idet funksjonene h( og H eventuelt kan være identiske.

Ifølge et annet karakteristisk trekk er fremgangsmåten slik at den hemmelige nøkkel x bestemmes før den allment tilgjengelige nøkkel Y, idet denne beregnes av formelen: Y = g<x> (modulus N).

Ifølge et annet karakteristisk trekk bestemmes nøkkelen Y før nøkkelen x, men størrelsen N velges til ikke å være et primtall. Ifølge et annet karakteristisk trekk ved oppfinnelsen er størrelsen r et vilkårlig tall. Oppfinnelsen omfatter også en fremgangsmåte for autentisering av den numeriske signatur (c, d) tilordnet en informasjonsmengde M, og denne fremgangsmåte er kjennetegnet ved å omfatte, idet man går ut fra at den allment tilgjengelige nøkkel Y, restleddet N, grunntallet g og spredefunksjonen H og derved størrelsen S er kjent:

- beregning av u ut fra forholdet u = g<d>y(<z*c>), idet Z = 2S,

- nøkkeltransformasjon med spredefunksjonen H av kjededannelsen av M og u, og - bekreftelse av at den oppnådde verdi er lik signaturen c i det tilfelte denne er autentisk.

Ifølge et ytterligere karakteristisk trekk ved denne fremgangsmåte er innfor-masjonsmengden M nøkkeltransformert med spredefunksjonen h] før nøkkeltrans-formasjon med spredefunksjonen H, hvoretter kjededannelse med u utføres.

Andre fordeler med og karakteristiske trekk ved oppfinnelsen vil fremgå av den detaljbeskrivelse som nå følger av en særlig utførelsesmåte, og det vises samtidig til tegningene, hvor fig. 1 viser et flytskjema for å frembringe en numerisk signatur, mens fig. 2 viser et tilsvarende skjema for autentisering av en numerisk signatur som er frembrakt slik det er illustrert på fig. 1.

Fremgangsmåten ifølge oppfinnelsen er blant annet egnet til å frembringe og fa bekreftet en signatur som er tilordnet en informasjonsmengde eller melding M. Uavhengig av de enkelte faser ved genereringen av denne signatur og bekreftelsen av den vil en autoritet som skal garantere sikkerheten i et overføringssystem fastlegge følgende generelle parametere slik: a) En størrelse N som danner en rest ved en divisjon og ofte angis med "modulus" N. Størrelsen av dette tall bestemmes ut fra betraktninger som har med sikkerheten av algoritmene å gjøre (i dag vil en tallstørrelse eller binærsifferlengde på 1024 b være et godt valg). Restleddet N kan være felles for en rekke brukere (eventuelt et meget stort antall) innenfor et krypteringssystem. Tallet kan i de forskjellige varianter være et primtall eller ikke, representere en elliptisk kurve eller generelt utgjør en gruppe som diskret eksponentbehandling er vanskelig å reversere. b) Grunntallet g kan benevnes en generator i undergruppen av den gruppe som fastlegges av restleddet N (restleddet som tall, et punkt på den elliptiske kurve, et

element i den valgte gruppe). Undergruppen som frembringes må ha stor "kardinalitet"

(>2S, hvor S er størrelsen av resultatet fra spredefunksjonen H, forklart nedenfor), men dekker ikke nødvendigvis hele gruppen for restleddet. Som dette ledd kan størrelsen g være felles for flere brukere.

Den såkalte kardinalitet må altså være stor, men kjennskapet til denne størrelse er ikke nødvendig for algoritmene for signatur og bekreftelse. Det er altså mulig å arbeide med eksponentieringen som en basisoperasjon og samtidig velge restleddet N som et produkt av primtall.

Størrelsene N og g er generelle størrelser eller parametere som settes opp en gang for alle og er felles for samtlige brukergrupper. De er ikke hemmelige, siden bare å kjenne dem ikke gir mulighet for noen å bryte ned algoritmens sikkerhet.

Den som har ansvaret for krypteringssystemet lar hver bruker få et par nøkler x, Y, idet x er en privat og personlig nøkkel som holdes hemmelig, mens Y kan kalles en generell eller privat nøkkel x, og det er bare brukeren selv som skal bruke den under etableringen av signaturen. Nøkkelen Y er særegen for enheten A som sender ut informasjonsmengden M. Hver bruker blir informert om avsenderens identitet ved mottakingen av en melding, og ved hjelp av et nøkkelregister kan nøkkelen Y brukes altså både av avsenderen (enheten A) og av mottakeren (enheten B). Nøklene x og Y er koplet til hverandre ved at Y er resultatet av diskret eksponentiering ved hjelp av grunntallet g, eksponenten x og restleddet N. Følgende likning gjelder således Y = g<x >(modulus N).

I de to versjoner som er beskrevet nedenfor og gjelder vlaget av x og Y har man den situasjon at den private nøkkel x bare er kjent av brukeren alene. Dersom imidlertid denne nøkkel x blir meddelt tredjemann vil problemet med den diskrete logaritme ikke lenger være noe problem, og sikkerhetssystemet er ikke lenger sikkert.

I den første versjon velges nøklene ved å la x få størrelsen S (for eksempel settes S = 160 b dersom en SHA-standard velges for spredefunksjonen H) og deretter beregnes Y ut fra formelen ovenfor. Denne versjon muliggjør bruk av mindre private nøkler x (160 b i eksemplet) og arbeider med en elliptisk kurve uten først å måtte beregne denne kurves kardinalpunkter.

I den andre versjon starter man ved å fastlegge Y, for eksempel ved å utlede denne nøkkel fra brukerens navn (se Maurer et Yacobi: "Non-interactive public-key cryptography" , EUROCRYPT'91, Lecture Notes in Computet Science, Springer-Verlag, vol. 547, pp. 498-507, 1991), og deretter utledes x ved en diskret logaritmisk beregning med restleddet N. Denne måte innebærer at man for restleddet ikke bruker et primtall, men et delelig tall N = pq slik at det er mulig å beregne logaritmen. Det kreves også at tallet N ikke avsløres slik at beregningen kan utføres av en vilkårlig person. Denne fremgangsmåte for å etablere signaturen sikrer at p og 1 ikke frigis, i motsetning til andre tilsvarende krypteringer. I de kjente måter må nemlig enhver kjenne kardinalen i den multiplikative gruppe modulus N, det vil si (p-l)(q-l), hvoretter p og 1 kan finnes.

Den som har ansvaret for krytperingssystemet legger inn en spredefunksjon H som er felles for samtlige brukere. Denne funksjon bruks for å nøkkeltransformere et vilkårlig tall med vilkårlig størrelse til et numerisk tall med sifferlengde S (b). Valget av H og S er uavhengig av algoritmen, og man kan derfor bruke enhver hittil kjent spredefunksjon.

Etter denne innledende fase av beskrivelsen skal vi nå betrakte to enheter A og B som ønsker å sette opp en sikret forbindelse for overføring av informasjon. I et første trinn som refererer til fig. 1 beregnes i enheten A en numerisk signatur (c, d) ut fra den informasjonsmengde M som ønskes sendt til enheten B. Dette trinn utføres utelukkende i enhet A.

Informasjonsmengden M som i prinsippet kan være meget stor kan nøkkeltransformeres i trinn 5 i skjemaet på fig. 1 ved hjelp av en spredefunksjon ht av en vilkårlig type for å gi et resultat m - hj (M). Deretter beregnes Z = 2S, idet S er fastlagt ved valget av spredefunksjon. Etter dette velges tilfeldig et tall r med sifferlengde T (b) (og med fast signatur T > 2S). I det neste trinn 20 beregnes U ut fra formelen gV (modulus N), og deretter kjedes tallene m og u sammen ved å la dem følge etter hverandre.

Videre utføres en nøkkeltransformasjon av det sammenkjedede resultat og ved hjelp av spredefunksjonen H. Resultatet c = H (mu) fremkommer som et numerisk tall med sifferlengde S fra resultatet. Deretter beregnes tallet d ved d = r + cx, og man har fått signaturen (c, d) for informasjonsmengden M. Signaturen sendes ut fra enhten A til enheten B, og da starter andre trinn i overføringen, illustrert på fig. 2. Dette trinn utføres utelukkende i (av) enheten B.

Etter at signaturen er mottatt sammen med informasjonsmengden m som hører til kan denne mengde nøkkeltransformeres ved hjelp av samme spredefunksjon h| som på sendersiden, deretter beregnes Z = 2S, idet S som før fastlegges ved valget av spredefunksjon, man beregner så differansen v = Z - c, deretter u etter formelen u = g<d>Y<v> (modulus N), og man kopler tallene m og u sammen i kjede.

Deretter nøkkeltransformeres på ny med spredefunksjonen H, slik at man får ut et tall med sifferlengde S, og resultatet er c\

Deretter undersøkes den signatur (c, d) som er sendt fra enheten A og sees spesielt om c = c\ og i så fall er senderen av informasjonsmengden M ikke noen annen enn enheten A, hvorved signaturen blir bekreftet, I motsatt tilfelle aksepteres ikke informasjonsoverføringen som riktig autentisert.

Claims (9)

1. Fremgangsmåte for å tilordne en numerisk signatur (c, d) til en informasjonsmengde (M) som skal overføres, idet man først definerer et restledd (modulus N), et grunntall (g), en offentlig nøkkel (Y) og en privat nøkkel (x), karakterisert ved at størrelsene N, g, Y og x står i forhold til hverandre på denne måte: Y = g<x> (modulus N), - nøkkeltransformasjon ved at man bestemmer en spredefunksjon H slik at størrelsen av resultatet blir S (b), - valg av et antall r på T siffere (b), idet T > 2S, - beregning av en størrelse u ut fra likningen u = gr * Y<z>, idet Z = 2S, - nøkkeltransformasjon ved hjelp av spredefunksjonen H, av kjeding av informasjonsmengden M og størrelsen u, idet det tall som kommer frem som et resultat brukes som signaturen c, og - beregning av signaturen størrelse d ut fra sammenhengen d = r + cx.

2. Fremgangsmåte ifølge krav 1, karakterisert ved at mengden (M) blir nøkkeltransformert med en spredefunksjon (hi) og deretter med en spredefunksjon H, hvoretter resultatet kjedes sammen med størrelsen u.

3. Fremgangsmåte ifølge krav 2, karakterisert ved at spredefunksjonene (h og h|) er identiske.

4. Fremgangsmåte ifølge krav 1-3, karakterisert ved at den hemmelige nøkkel x bestemmes før den allment tilgjengelige nøkkel Y, idet denne beregnes av formelen: Y = g<x> (modulus N).

5. Fremgangsmåte ifølge krav 1-3, karakterisert ved at den offentlige nøkkel (Y) fastlegges før den private nøkkel (x), og at restleddet (N) velges som et tall som ikke er et primtall.

6. Fremgangsmåte ifølge krav 1-5, karakterisert ved at størrelsen ® er et vilkårlig tall.

7. Fremgangsmåte for autentisering av en numerisk signatur (c, d) som er tilordnet en informasjonsmengde (m), idet signaturen er frembrakt ved en fremgangsmåte ifølge ett av kravene 1-6, karakterisert ved at man går ut fra at den allment tilgjengelige nøkkel Y, restleddet N, grunntallet g og spredefunksjonen H og derved størrelsen S er kjent: - beregning av u ut fra forholdet u = gdy(zc)> idet Z <=> 2S, - nøkkeltransformasjon med spredefunksjonen H av kjededannelsen av M og u, og - bekreftelse av at den oppnådde verdi er lik signaturen c i det tilfelle denne er autentisk.

8. Fremgangsmåte ifølge krav 7, karakterisert ved at mengden (M) er nøkkeltransformert, først med spredefunksjonen (h|) og deretter med spredefunksjonen (H), hvoretter resultatet er sammenkjedet med størrelsen (u).

9. Fremgangsmåte ifølge krav 8, karakterisert ved at spredefunksjonene (H) og (hi) er identiske.