NO962672L - Fremgangsmåte for å etablere en felles nökkel for autoriserte personer ved hjelp av en sentral - Google Patents

Description

Foreliggende oppfinnelse angår en fremgangsmåte av den art som angitt i innledningen til krav 1.

En slik fremgangsmåte er f.eks. angitt i DIN EN 50 094 for Pay-TV-System Eurocrypt. Den tjener til etablering av en felles hemmelig informasjon k (nøkkel) for autoriserte personer av en større persongruppe P = {P]Pm} ved hjelp av en sentral instans Z (sentral).

En sentral avgjør hvilke personer av en persongruppe er autorisert. Fremgangsmåten garanterer at kun disse personene kan få, hhv. er berettiget til å få denne nøkkelen. Denne autoriserte personen er i det påfølgende betegnet med Pi,..., Pn(slik at det gjelder n < m). Meldingen fra sentralen til brukeren kan sendes via et kringkastingsmedium (jordbundet radio-, satelitt-, kabelnett) eller andre ikke-sikre kanaler til personen P.

Det er kjent anvendelse av en symmetrisk koderingsalgoritme (for definisjon av en symmetrisk koderingsalgoritme, jfr. og A. Beutelspacher: Kryptologie, Vieweg Verlag 1994). Hver person Pj av P er tilordnet en personlig nøkkel kj, som kun personen og sentralen kjenner. Sentralen Z velger kun nøkkelen k og koder den for i = 1,N med de respektive personlige nøklene kf.

Dette kryptogrammet sendes til den autoriserte personen Pj, som kan beregne nøkkelen k, idet kryptogrammet dekoderes:

Denne fremgangsmåten anvendes f.eks. ved Pay-TV-System Eurocrypt (DIN-EN 50 094) for etablering av en systemnøkkel.

Ulempen ved denne metoden er at nøkkelen k overføres kodet. I mange land er anvendelsen av en kodealgoritme satt under rettslig beskyttelse. Dette kan f.eks. føre til at den ovenfor anvendte algoritme E må være svært svak.

Oppfinnelsen har derfor til oppgave å tilveiebringe en metode som kan anvendes uten betenkeligheter og som samtidig er tilstrekkelig sikker.

Denne oppgaven løses ved en fremgangsmåte av den innledningsvis nevnte art hvis karakteristiske trekk fremgår av krav 1.

Ytterligere fordelaktige utførelsesformer av oppfinnelsen fremgår av de øvrige uselvstendige kravene 2 til 4.

Oppfinnelsen skal ved det påfølgende utførelseseksempel beskrives nærmere hvor det ved hjelp av metoden på symmetrisk kryptografi etterlignes funksjonaliteten til den ovenfor beskrevne metoden uten anvendelse av koderingsmetoden. Derved kan det ved opprettholdelse av rettslige bestemmelser forbedre sikkerheten ved koderingsfordelings-mekanismen.

Den her beskrevne oppfinnelsen bygger på en kombinasjon av en nøkkelstyrt enveisfunksjon med en terskelmetode (A. Shamir; How to Share a Secret. Comm. ACM, vol. 24, nr. 11, 1979, side 118-119).

En enveisfunksjon (jfr. såkalt posepakker) er en funksjon g (•), som lett kan beregnes (dvs. den kan lett beregnes for hver verdi a er lik g (a), men hvor det praktisk talt er umulig å finne til en gitt bildeverdi b et opprinnelig bilde a, slik at g(a) = b gjelder. En nøkkelstyrt enveisfunksjon er en enveisfunksjon f (•,•) med to argumenter k og a, idet verdien k kan anses som nøkkel.

Med en (n, t)-terskelmetode kan man spalte en hemmelighet k i t deler, som kalles "Shadows", slik at hemmeligheten kan rekonstrueres av respektive n til t Shadows.

Som eksempel på en slik (n,t)-terskelmetode skal i det påfølgende et polynom at n-1 grad betraktes, hvor t = 2n -1 støttesteder skal velges som Shadows. Ved angivelse av n støttesteder, dvs. av n par (xj, yj) (i = 1,n) av elementer til legemet med forskjellige x-komponenter, defineres et entydig polynom av n-1 grad. Dette polynomet skjærer y-aksen i et entydig definert punkt.

For å etablere en felles nøkkel for autoriserte personer ?\,Pn tilordnes først hver person Pj av P personer under anvendelse av den personlige nøkkelen kj et støttested (aj, bj). Dette kan foretas på forskjellige måter:

1- (aj, bj):=G>kj),

2. (<a>j,<b>j)<:><=>(j, g (kj)) for en enveisfunksjon g (•),

<3.>(<a>j, bj):<=>0»f (r>kj)) for en nøkkelstyrt enveisfunksjon f (•, ■) og et tilfeldighetstall r, 4. (<a>j,<b>j):=(f(r, lj), f(r, lj')) for en nøkkelstyrt enveisfunksjon f (•, •), et tilfeldighetstall r og kj = (lj, lj'), osv. Ved hjelp av støttestedene (aj, b]) bestemmes et polynom p(x) av n-1 grad. Det entydige snittpunktet

til dette polynomet med y-aksen er den felles nøkkelen for Pj,Pn. For at de

autoriserte personene P|,Pn skal kunne beregne denne verdien k velger sentralen n-1 ytterligere støttesteder ( c\, d\),(cn_j, dn.\), som må være forskjellig fra (aj, bi),..., (an, bn). Disse kan sendes sammen med den for beregning av støttestedene nødvendige tilleggsinformasjon (f.eks. tilfeldighetstallet r av 3) til alle personer ut av P personer.

Kun de autoriserte personene Pj (1 < j < n) kan nå beregne nøkkelen k. For dette formål føyer pj mengdene (cj, d\),(cn -1, dn - 1) til støttestedene (aj, bj), som han og sentralen kan beregne, da kun denne personen og sentralen kjenner den personlige nøkkelen kj. De således tilveiebrakte n-støttestedene bestemmer polynomet p (x) og dermed også tallet k = p(0).

De ikke-autoriserte personene Pj (n+l< j < m) kan ikke beregne nøkkelen k, da de av dem beregnbare støttestedene (Aj, bj) ikke ligger på kurven for p (x).

En anbefalt realisering av den her viste oppfinnelsen skal for utledelse av støttestedene anvende en nøkkelstyrt enveisfunksjon, altså en variant av metodene (3.) eller (4.) for å utelukke et mulig angrep som ville være mulig ved anvendelse av den svakere varianten (1.) og (2.). I dette tilfelle kan det bli vist at en ikke-autorisert angriper etter denne metoden etablerte nøkkel k kun kan bryte denne når han kan snu enveisfunksjonen.

Claims (4)

1. Fremgangsmåte for å etablere en felles nøkkel (k) for autoriserte personer, idet mengden med autoriserte personer er en tidsmessig seg endrende delmengde av en totalmengde av abonnenter, ved hjelp av en sentral (Z) via ikke-sikrede kanaler, fortrinnsvis et radiomedium, hvor abonnentene har respektive personlige nøkler (kj), som kun er kjent for abonnenten og sentralen, karakterisert ved at i sentralen utledes fra den personlige nøkkelen til hver av de n autoriserte personene en delhemmelighet (Shadow) (sj), at i sentralen blir ut fra totalheten til den således tilveiebrakte Shadow for autoriserte personer konstruert en (n, t)-terskelmetode (med t > 2n-l), at i sentralen ved hjelp av denne (n, t)-terskelmetoden beregnes ut fra n Shadow'er ( s\... sn ) en nøkkel (k), at data for konstruksjon av (k), som består av de for utledelse av Shadow (sj) fra den personlige nøkkelen (kj) nødvendige data og av n-1 ytterligere Shadow'er til (n,t)-terskelmetoden, som skiller seg fra Shadow til de autoriserte personene, overføres over den ikke-sikrede kanalen, og at de autoriserte personene mottakersidig utleder nøkkelen (k) fra sin personlige nøkkel (kj) til tilordnede Shadow'er (sj) og ut av denne Shadow kan beregne nøkkelen (k) ved hjelp av n-1 videre Shadow såvel som (n,t)-terskelmetoden.

2. Fremgangsmåte ifølge krav 1, karakterisert ved at ved utledelse av delhemmelighetene (Shadow) (sj) i sentralen utledes fra den personlige nøkkelen for hver av de n autoriserte personer under anvendelse av en felles parameter (r) og respektive personlige nøkler (kj) under anvendelse av en enveisfunksjon (f( delhemmeligheten (Shadow) i form av Sj = f (r, kj).

3. Fremgangsmåte ifølge krav log2, karakterisert ved at (n,t)-terskelmetoden realiseres ved hjelp av et polynom av n-1 grad, som anvendes for utledelse av Shadows ved hjelp av n støttesteder, defineres entydig, og ved ytterligere Shadows utvinnes derved, og at sentralen velger punkter på kurven av polynomet som er forskjellig fra de ut av Shadows til autoriserte abonnenter tilveiebrakte støttesteder.

4. Fremgangsmåte ifølge krav 1, karakterisert ved at fremgangsmåten anvendes for suksessiv etablering av et hierarki av nøkler.