Kryptografie in Theorie und Praxis: Mathematische Grundlagen fur Internetsicherheit, Mobilfunk und elektronisches Geld 3834809772, 9783834809773 [PDF]

Zitiervorschau

Albrecht Beutelspacher

I Heike B. Neumann I Thomas Schwarzpaul

Kryptografie in Theorie und Praxis

Albrecht Beutelspacher Th omas Schwarzpaul

I Heike B. Neumann

Kryptagrafie in Theorie und Praxis Mathemati sche Grundl agen für Internetsicherheit, Mobilfunk und elekt roni sches Geld 2., überarbeitete Auflage STUDI UM

VIEWEG+ TEUBNER

Bibliografische Information der Deutschen Nationalbibl iothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Natlonalbibfiogratie: detaillierte bibliografische Daten sind im Internet über abrufbar .

Profe ssor ör. Alb recht Beutelspacher ur, Thom as Schw ar zpaul Universitä t Gießen Mathematisches Instit ut Arndtstraße 2 D-35392 Gießen E-Mail: [email protected] t [email protected]

Or. Helk e B. Neumann Mühlendamm 45 a 22087 Harnburg E-Mail: [email protected]

1. Auflage 2005 2., überarbeitete Auflage 2010 Alle Rechte vorbehalten © Vieweg+Teubner I GWV Fachverlage GmbH, Wiesbaden 2010 Lektorat: Ulrike Schmickler-Hirzebruch I Nastassja Vanselow Vieweg+Ieubner ist Teil der Fachverlagsgruppe Springer Seience-Business Media. www.viewegteubner.de

,.rl - j .'ln -j+ k =

j:= Q

L

- CjI' k+j = - .'III+k ·

j:= O

Die letzte Umformung folgt au s der Rekursionsgleichung für den (n + k)-te n Zusta nd des linearen Schieberegisters. Da ra us folgt ( 8'1 +~'

+d

ll

+d

Somi t gilt : y(X ) = j* (X )S(X ) = a lles gezeigt .

= (Su+k - 8 n H ) = O. E :':01 (8i

+ dz) X i und

G rad (y)

< 11,

und

t 'l'

ist

0

Aus den bisherigen Üb erlegu ngen folgt: Ha t ein e line are Schieberegisterfolge d ie Perioden länge r, :-0 gilt

S eX ) = y(X ) = r eX )

80

+ 81 X + S2 X2 + ...+ Sr _I X

r

-

1

1 - X'

wobei Gnu l(g ) < n ist . Diese Gleichung ver knü pft algebraisch d ie Registerl ä nge n mit der Periodenlänge r, Ins bes ondere stellt d ie Gleichung ei nen Zusa mmenhang her zwisc hen dem Rü ckkopplungsp olynom und der Peri od enl änge jeder Folge , die VO ll diesem Reg ister erzeu gt wird . Damit sind wir in der Lage, ans den Eigenscha fte ll der R ückkopplungsfunkt ion a uf d ie Perioden länge zu schließen. Wir eri n nern zun ächst an den Begriff der Ir red uzibilitä t : Sei K ein Kör per. Ein Pol ynom f E K [X] heißt irreduz ibel , wen n für jede Da rst ellu ng f (X ) = g(X )h(X ), e. h E K (X] , gilt: Entweder ist 9 oder h eine Ei n h ei t . Ein e Ein heit ist ein K örperelement ungleich O. Das nächste Lemma zeigt . dass wir mit einer Zerlcgung VO ll fa uch stets ein e Zcrlcgung des rezip roken Poly noms f * ha ben :

60

6 Stromchiffren

Le mma 6.3 Es seien

I , g , ue

K [X J. Dan n gilt:

f (X ) ~ q(X )" (X ) .. r(X ) ~ g' (X )" ' (X ).

o

Beweis: vgl. Übungsa ufgabe 1. Aus Lemma G.;! folgt , d ass ei n Poly nom

f

ge n au d a nn irred uzi bel ist , wenn auch das rezi proke Polynom einer Einh eit gerade die Einheit seihst ist. Das Polynom f hat also gellau dann nur Zcrlcgungcn . VOll denen ein Fa ktor ein e E in heit ist, wenu a uch f * nur solc he Zerleguugcn ha t.

r irred uzib el ist. Der G rund dafür ist ,

dRSS

Die letzte Tella ussa go. die wir für den Hauptsa tz benötigen. betrifft den Grad P Ol.YIl OIllS. Ist f ei n irreduzibles P oly nom . so ha t d as rezi proke Polynom von f den gleichen Grad wie f:

d es reziproken

Lem ma 6.4 Es sei n ;::: 2 und f E J(!XJ mi t f (X ) = 'L jl=ocj X j , er! irreduzi bel ist, so gilt Co =I- 0 und Grad(f* ) = Grml(f ).

f

Beweis: \Vir zeigen zunäch st , dass Dann is t

f (X )

~t

#- 0 gilt.

Co

c; X;

j~O

~X

i-

O. ~Ven n

Augcnoun ucn , dem wäre nicht so.

(:f

C"i +1 Xj ) .

j~O

Dies ist eine Zcrlcgung VOll f , wobei keiner der Fa ktoren ein e E inheit ist (denn n ~ 2 und C-n #- 0). Damit ist f nicht irre d uzibel . und wir haben einen Widerspruch zur Voraussetzung. Xuu zeigen wir: hat den gleichen Grad wie f . \ \'i r betrachten daz u

r

j* (X ) = Der Lcltkocfflzlcn t

VOll

r ist

n

L cj x n- j = L cn_j X j .

j-e

C lI _

n

=

j ~O

Co

#- O. Damit

ist G ra d (j *) =

11

= G rml(J ).

o

Um den Ha uptsa tz kompakt formulieren zu können, führen wir jetzt noc h den Begriff des Exponenten eines POlYIlOIllS ein: Defin it io n 6 .5 Fiir ein irreduzibles Polyn om f E /{ [X J heiß t die kleinste nuiii rliehe Zahl e mit f I (x e - 1) der Exp o nent von f . Bemerku ngen

a ) Jedes Pol ynom

f

E K [oE] besi tz t einen Exponen ten.

b) \Venll f I (xe - 1) gilt , so folgt aus Lemma 6.3 sofort , dass für das rezi proke R ückkopplu ngspolynom f* I ( 1 - .x") gilt , denn es ist:

(xe _ 1)'

~

(1 _ X ").

G.:! LilleHre Schieberegister

GI

Dam it können wir jetz t den en tscheidenden Sa tz über d ie Periodenl änge einer linearen Sch ieber egisterfolge form ulieren:

Sat z 6 .2 Es sei j( X) das R iickkoppl'U lIgspolY1lom eine r linearen Schiebcronsterfolye mit R eyisted iinye n. trenn / irreduzibel und c der Exponent von [ ist, dann haf j ede 1Ion (fiesem Schicbc reqister erzeuat e Folge (mit Ausnahm e der Null/alge) die Periode c. Beweis: Es sei (.Oeine be liebige Folge , d ie vomlinearen Schieberegister erzeugt wurde u nd nicht d ie Xul lfolge ist. Zu zeigen ist , d ass sie d ie Periodenl änge e hat. Da ( Sdi~ O beliebig gewählt wurde, ha t d an n jede Ausgabefolge m it Au snahm e der Xullfolgc di e Periodenl änge e. \ Vi r wissen be re its. d ass sich die erzeugende Fu nkti on d ies er Fo lge folgendcnnason darstellen lässt :

S(X ) ~ g(X ) ~ j' (X)

' ... > Um > Um + l = () und ql ' q2' ..., 11m E N mit llO II I

= qj(11 + ll2

= (12(12 + (13

0 < 112

< UI

O < 1l:~ < U 2

Om_ 2 = qm _ IOm _ 1 + Om

o
(1') =

n - ~( n) -1 + J(n

1>(n)

I )'

41>(n).

Da der Angreifer 11 und (jJ(n) kennt , kan n Cl' mitt els d ieser Gleichu ng also 1>(p) best immen. Wegen q;(p) = p - 1 hat er dam it auc h P. und wegen 11 = Wl kann er a uch q berochnon . 0

Satz 10.4 Gcgeben se i ei ne Z ahl n , die das Produkt zwe icr Pri m zahlen ist. Fiir ) c(len effizienten A ngreif er A sirul äquivalent:

(i) A kann bei Eingabe von n die Pri m f akto ren p und q t'on 11 bestimmen. (i i) A knn 1l bei. Eingabc non. 11 und eine r zu q,(1I) teil erjrenulcn. Z ahl e eine Z ahl d berechnen m it cd es 1 (mod q,( n )).

10.5 Die Siche rheit d es RSA-Algorithillus

127

Beweis:,,(i) ::::}(ii)":Dies folgt m ittels des erweit erten Euklidischen Al gorithmus gena uso wie be i d er Schlüs sele rzeug ung de s RSA-Verfahrens. ,,(ii)::::}(i)": Angono nuncn , d er Algo rit hmus kann bei Eingab e VOll n und c d ie Zahl d bestimmen . für d ie gilt: ed es 1 (mod 4J(n)) . Au s ed es 1 (mod 4J(n)) folgt ed - 1 = h jJ(n ) für ein k E Z . Angenommen, de r Angreifer ka n n ein e Za hl n E Z ~ und eine na t ürli che Zahl s find en m it d en Eigens cha ft en: (12.,

== 1 (mod n)

((~ :t

± 1 (mo d n ).

(10.;1) (10.4 )

Da n n kan n man a us J O . :~ Folgendes schli cken:

I (u 2 ,' S 11 I ( U -

11

1), also

1)(aS + 1).

Ans 10.4 folgt alx-r. d ass n wede r (a S - 1) noch (a S + 1) t eilt. Da n a be r d as P rod u kt teilt, ist in jed em der Faktoren jeweils genalt einer d er P rimfaktoren von n ent ha lten. Berechnet mall also d en größ ten gcun -iusamcn Teiler von n u nd (US _ 1), so find et Ulan einen Pri mfa ktor VOll n. Xla n kann zeigen , da ss sich t'i und u effizien t fiudou lasscn. wobei der Algorithmu s p roba bilis t isch ist , man ha t also unter Um st änden einige Fehlv ers uche. \Vir wollen d ies hier a ber nich t explizit a usfü hren. Deta ils finden sich ZUlU Beispiel in I~ ~ 0 Mit de n let zten Iw idPII S ätzen ist gezeigt , das s kein Angreifer au s einem öffcntlichen Schlüssel d CII zugehörigen privaten Schlüssel berechnen k ann , es sei d enn , er kan n faktorisicrc n. Eine Konsequenz a ns den beiden vorangegangenen Sätzell ist , dass jeder Teilnehmer nicht nu r seinen eigenen öffent liche n Exponenten wählen IllU SS , sonde rn auch einen eigenen Mod ul. Die Sätze JO. :~ und JO.4 beweisen , dass das RSA-Verfa hrell die P ublic-KeyEigenschaft besitzt . Das ist abe r nicht äquival ent zu m Brechen des RSA-Verfa hrcns . Denn ein Angreifer int eressie rt sich m öglicherweise nicht für d en privaten Schlüssel . sonde rn nur für den Inha lt der Cehci mtcxt e. Um d ie Gehe im te xte zu entsch lüsseln gibt es a ber vielleich t ei nen Algori thmus, de r oh ne d ie Kenntnis des privat en Schlüss els auskommt. Xla n konnte hisher nicht zeigen, d as s Ulan nur d an n ents chlüsseln k an n. wen n mau d en pri vat en Schlüssel kennt . D ie Vermu tung. d ass es keine n effizient en Algorit h nms g ibt , de r a us einem Geheimt ext den passenden Kla rt ext best im men kann. ist in d er Kry p togra fie so wich ti g. d ass sie ei nen eige nen Xa mcn ha t: di e

R SA- AllIlahlue . Annahme 10 .1 (RS A-A n nah me) Es sei n eine aus zwei ve rschiedene n Prim zahlen]l und (j zusumm cnccsctete Zahl, wobei die beiden Primzahlen jeweils eine Länge von k B it haben. Weiter'hin sei ei ne zu ,p( n) teilerfremde Zahl e gegeben. Dan n gilt: Für jed en prclnbilistischen polynomiellen A lgo1'i.t.lw l1tS A i8l. di e Wahrsch einlichkeit, dass er bei Einyabe von k, n , e uud y mit ;ce mod n die Zahl r

10 Der IlSA-A lgorit hllllls

128

bn 'Cchn cn kan n. vemachlässigbar. Das heißt, fü r jedes A gibt es eine vernachlässigbare Fllnl:tion 1/ /lnd eine natürliche Zah ll'o , so dass für' alle k 2: ko gilt:

P [A(k. TI, e, z " mod n) =:t

I:t Eil Z;'J < v(I.: ).

Xlit a ndere n Wort en ve r m utet man , dass es s ich bei d e r a SA-Funkt ion um ei-

ne Tra pdoor-Einwcgfunktion handelt. Ein Angn-ifer, der nur den Schlüssel (n, e) und oiucn Geheim text y = J: e mod n ken nt , hat pra ktisch keine Cha nce , den Urbildpunkt J' zu lx-st immen . Es gi ht aber eine Zusetzinformation. d ie die Invcrti erung der Funkt ion mög lich macht , nä mlich die Primfaktorzcrlc gung VOll n bea ichuugswcisc der priva te Schlüssel d. Für d ie Sicherheit einige!' P rotokolle braucht man manch ma l nicht nur d ie R SA-AllI laIUllC, sondern ein e stä rkere Vermu t un g: E in Angreifer kann nicht einmal da n n einen Urbil dpun kt bestimmen , wenn er selbst den öffentlichen Ex ponenten wählen kann.

A n na h m e 10.2 (Star ke R S A- Aunahme ) Es sei n eine aus zwei Pri m zahlen p und 'l zusom mc noesetete Zahl, wO/lei die beiden Primzahlen j eweils eine Liinge 'V on k Bit haben. Dan n gilt: Fiir jed en pmbabilistischclI polyuomiellen Algorithmus A ist die Wahrscheinlichkeit, (lass er bei Einyabe von k, 11 und einer Znjalls zchl y E Z;, zwei Zahlen :r und C mit y = ;ce mod n berechnen kann , 'Ve1i wchliissig/mr. Das heißt , für je des A gibt es eine vem achliissigbm"€ Funktion /1 und eine natürliche Zahl ko, so (lass für alle k 2: ko gilt:

P [A(k, n, y ) = (:1', e) m it x'" mod n = y I Y EH Z;J < v(k). Wi r werden im Kap itel 1:-1 den Sicherheitsbeg riff bei Public-Key- Vcrschltissoluugsverfahren forma l definieren und in diesem Zusammenhang di e Sicherheit des RSAVcrschl üssc lungsvcrfahrens genaller analysicrcn.

10.6

Homomot-phie d er R SA-Fllnktioll

Die RSA-Ven whlüsslllllg ha t eine besondere Eigenschaft , de nn ma them a tis ch gesehen ist die n SA- Verschl üssel ung ein Homomorph ismus. Anders au sged rückt he~ d eutet d as , dass das P ro d u kt zwcier Geheimtex te gerade der Geheim text d es P rodukt es ist . Gen euer gesagt gilt , dass d as Prod ukt zweier Ge heimt ex te d er Verschl üsselung d es P rod uktes zwcier Klartext e entspricht.

Sa tz 10.5 Es sei ein öJJcntlichf;7" RSA -Schliissd (11, c} yeyf,bm . Dann ist die A bbildung R S A : Z:l - Z~, ./: -> r", ein bij ektillc1' Gruppenhomomorptusmus, also ins besondere eine Permutation auf Z~ . Beweis:

10.7 Konkret e Juiplcment ierungcn

129

1. Bijektivität . Es genügt , die Iujoküvit ät zu zeigen , da Z;, ein e endliche Xlongc ist. Es sei d der zu (11, e ] gehörige priva te Schlü ssel. Gegeb en sei ein y E Z ~ . Angcnonunon. es gibt .r t :1:z E Z;, mit

R S A(x d = .rl = y, RS A(x z) = x; = y Dann folgt aus dem Satz

Eulcr (10. 1):

VO ll

2. Homomorphic. Gegeben seien

.T1 ,

RSA(:q )· RSA(:rz) =

x, = :rj'd =

yd

=

x'i/ =

za ,

.ca E Z;,. Es ist :

xI ' :c2 =

(X I '

:cz)e = RSA(x l . xz ).

o Die Homo morphic- Eigen sch aft der RSA -Fu nktion ist ambivalent: Ein erseit s ist sie in vielen Anwend ungen nüt zlich , denn d urch sie lassen sich viele erw ünschte Eigens chaften von P rotokollenleicht umset zen . Anderers eit s ist sie oft die Ursache fiir Angriffe a uf Prot okolle.

10 .7

Konkre t e Im ple m entie run ge n

Obwohl die Sicherheit des RSA -Algorit hmus g ut unt ers ucht ist und er a llgemein a b sicher gilt , ist eiuc konk ret e Implement ier ung st ets sorgfältig zu überprüfen. Dass ein sicherer Algorit hmus in bcsti unut eu Situationen elennoch unsicher verwendet werden kann , lässt sich a n folgendem Beispiel verdeut lichen: Aus Effizienzgründen wurde vorgeschlagen, fiir a lle Teilnehmer den öffentlichen Schlüssel e = :3 zu wählen . Angcnonuucn. es gibt d rei Teilnehmer A , B, C mit den öffentlichen Schlüsseln (n A, :3), (nu , :3), (ne, S}. ~ Ia n kann davon ausgehen . da,>s die drei Moduln nA, 1I/J. lIe paarweise tei lerfremd sind. (Andern fa lls wären bereits zwei davon fak torisiert .] An gonounucn, alle dr ei Teilnclunor erhalten d ie gleiche Nachricht m , die jeweils unter dem öffentlichen Schlüssel e = a chiffriert worden ist : CA

= m.3 (mod

HA )

eH

= m:l(lllod

l1U )

3

Ce = m (mod »c ) .

Ein Angreifer fängt diese drei Chiffrate ab. EI" ken nt die Xachricht ru nicht , weiß a ber, dass alle d rei Geh eimtext e den gleichen Inha lt haben . Er k ann sich mit dem chinesischen Restsa tz ein m' be rech ne n mit. 0 < m ' < llA . nLJ . »c und m' == cx (lllod llx ) für X E { A, ß , Cl.

ian

10 Der IlSA-A lgorit hllllls

Fa lls {) :s: 111 < min{n". 1l/J, He } ist. so ist 111 3 < H A ' lllJ ' nc u nd d am it m ' = m:l (in Z). In Z ist es j edoch einfach. d ritt e Wurzeln zu berechnen. Heute wä hlt man oft e = 2 16 + 1 als öffentlichen Exponenten . Dieser Augriff funktioniert offens icht lich nur in einer sehr s pez iellen Sit uat ion . Sie ist a be r nicht unrealistisch. G erade in elekt ronisc hen Kon unuuikationssystcm en werden Xac hri chtc n häufig automa t isch an mehrere Teiln ehmer versch ickt lind bieten dem An greifer gc na u die von ihm gewünschte Sit ua t ion . Allerdings ist der Angr iff vcrhält nis mälsig schwach , denn der Angreifer kann da nn nur eine Xach rlcht ents chlüsseln. D ie Sch lüssel der Teilnehmer werden nicht a ngegriffen . Dei diesem An griff wurde nicht d irekt ( \('1' RSA-AJgor ith llllls a ngegriffen. sondem nur ein konkret es Anwenduugsszeuario. \ Vir werden auf Angriffe dieses Ty ps noch einma l a usfüh rlich in Kapitel 10 zurü ckkom men .

10 .8

Ü b u n gen

J . 111 der P raxis ist es heute üblich . d en RSA-),Iod ul 11 in der Gröf,e VOll 20.,\ 8 Bit Zll wählen . Wi e viele Bits hzw. Dezimalstellen müssen de mz ufolge die P rimzah len l' und (} haben'?

"b {mod n ) => f ra) "f( b) [mod n). (b) c E Z\ {O} und nc es bc ( mod 1Ic) => ([ es b (mo d 11) . (a) f E ;'(ll ·b) = 4J(a)·q.,(b). 0. Beweisen Sie den chinesischen Restsat z }O.2. '/11. E Z~ und e E Z ,p(n ) , 11 habe }02.,\ Bits. Berechnen und ver gleichen Sie die Laufzeiten für die Berech nun g VOll 'I1l f ' mod 11 m it de m Chinesischen Res tsa tz und ohne ihn.

10 . Es sei

10.8 Übungen 11. Nach d er ersten Folgerung aus d em Sa tz von Euler gilt für jede P ri m zah l p und jede zu p teilerfremd e Zahl n: fl P- 1 == 1 (mod p ). Die Umkehrung des Satzes gilt nic ht : • E ine ungerade zusa mmengesetzte Za hl 11 mit a 1l - 1 ss 1 {mod n ) hei ßt Feemat sch e P seudopr imzahl zur Basi s a, Zeigen Sie: :l·H, 56 1 u nd 645 sind Fernratsche Pseudoprhn za hlen zur Basis 2. • E ine ungerade zusam mengesetz te Zahl 11 mit (/ 11 - 1 es 1 ( mod 11) für al le a E N m it qyT(a. ll ) = 1 hei M Carm ichael-Za h l. Zeigen Sie: 561 ist eine Cermichael-Zahl.

12. Gibt es heim RSA-Verfahren .schweche Schlüssel", das heißt Exponenten e mi t m " == 111 ( mud n )?

1:12

11

Der diskrete Logari thmus, Diffie- H ellman-S chlüssel vereinbarung, E IGamal-Systeme

Wir hab en im letzten Abschnit t ein P ublic- Kcy-Systcm . nämlich de n RSA-Algontlnuus kennen gelernt; dessen Sicherhei t beruht a uf dem Fa ktoris lcrungsp roblem. Diffic lind Helluran . di e Erfi nd er d er P u blic-Key-Kry pt ogra fie, hab en in ihrer Veröffentlichu ng von 1976 ein a nderes ma thema tis ches P ro blem benutzt , IIlIl ein Public-Key-S ystem . die Diffit'- Helhnall-SchliissP!vef eillharung, ZII entworfen: d en di s kreten Logarithmus. Dabei handel t es sich um das folgende Prob lem: Gegeben seien eine Primzah l p und zwei ga nze Zahlen .'1 , lt- Gesu cht ist eine ga nze Zahl :r mit de r Eigenschaft y X mod P = y . Gesucht ist also der Logarithmus VO ll !J zu r Bas is y , allerdings nich t über den reellen Zahlen . so ndern ruodulo einer Prim zahl, d aher au ch d er Xe mc diskreter Logarit hmus. Bis heu te kennt man keinen effi ziente n Algorithmus , der d ieses P roblei n lÖSCH k ann. W ie di e Faktortsierung gilt auch (las P ro blein des diskret en Logarit hmus heute als .schwierigcs" Problein. 1!:JS4 hat da nn Tehcr ElCamal ein Verschlüsselungs- und ein Signaturverfa hren veröffent licht. deren Sicherheit auf dem P rob lein des d iskreten Loga rithm us heruht.

11 .1

Überb lick ü be r d ie Diffie-Hellman- Schlüsselve re inba rung

Mit der Diffie- Ilcllman-S chliisscl verc inb a r ullg lässt sich ein ty pisches P roblcm d er sy unnet rischcn Kry pt ografie sehr elegant lösen . Um eine sy m metrisc he Verschlüsselung d urchführe n zu können . m üssen Sende r und Empfä nge r zunächst ei nen Schlüss el vereinba ren . was d ie Möglichkeiten einer spontanen Kommunikat ion zwischen Sende r u nd Empfänger st ark einschränkt. Bei d er Diffie- Helhna n-Sehl ib sel verei nh arung können zwei Teilnehmer A u nd B öffentlic h ein gemeinsames Geheimnis erze uge n . Das P rotokoll funk tioni ert wie folgt: Die beiden Teilneh mer einigen sich zunächst a uf eine P rim zahl J! uud eine ga nze Za hl g . Diese Za hlen kö nnen öffentlich vereinbart werden . An schlickcnd wählt jed er d er lx-idon Teiln ehmer geheim eine Zufa llszah l a hzw. bund poten ziert y mit seiner Zufall szahl: "A := s" mod p und !l ß := gb mo d 1J.

11.2 Xlat hcm a tischc Details

(J

Eu {I , . . . , p- l }

berechn et :

"A

:= 9" mod p

b En

~

hn

{l " " ,p -l }

be rechnet : h. n := rl m od

]J

lx-rechnet :

berechnet : h'}3 mo d p (= 5/'" mod 1')

h~l mod p (= g"b mod p ) hg mod p = J( = h~ mod p

gemeinsamer Schl üssel

Abbildung 11 .1 Diffi('-HeUlllllu-Schliisse!w!"einhanmg

Diese Werte schicken sich d ie Teilnehmer geg enseitig zu. Auch d ies kan n wieder öffen tlich geschehe n. Im letzten Sch ritt p otenzieren bcide d ie ges endeten Zwischencrgobnisse m it ihren jeweiligen Zufallszahlen. Das heifi,t , A berechnet h R tnod p, und ß b erech net h~l mod p. Wie man leich t sieht , erhalten boldo d as gleiche E rgebnis Je den n es ist;

l/h mod l' =

d'"

mod

]J

= gilb mod l' = h~l mod p.

A und ß kön nen damit in a ller öffcn t lichkcit ein ge meinsa mes Gehei m nis erzeuge n.

Denn ein An greifer müsst e , u m a n das Ceheinmis zu gelangen, ans s" mod p u nd das Geheimnis g"h mod p ben-chucn können. Man vermutet , d ass es hierfür keinen effizienten Algorit hmus gib t .

rl mod p

11. 2

Mat.hemat.ische Details

Es sei im folgen d en p stets eine P rim zahl. Dann ist Zp ein Kö rp er lind Z; = Zl'\ {ü] zusam men m it der Mul t iplikation eine G ru p pe. Diese Grupp e h at IZ;I = q;(p) = p - 1 Element e, da mi t ist di e O rdnung d ieser Gruppe ]J - 1. Xa ch d em Satz VO ll Eu lcr gilt dann für a lle Eleme nte (I aus Z; :

a P- 1 =: 1 ( m od 1').

11 Der diskrete Logar ithmus Es han delt sich hier soga r uni eine zyk lische Gruppe, das bedeu tet , dass es tni ndcstcns ein erze ugen d e s Element in dieser G ruppe gibt. Es gibt a lso mindestens du Element q in Z;, mit der Eigenschaft , dass sich j edes an dere Element. aus Z;, als eine Potenz von g schreiben lä sst . Ein erzeugendes E lement heißt oft au ch eine Primi ti v wurzel (cngl. gen erator ). Erzeugende Element e in Z;, sind gcna ll d ie E lement e der Ord nung l' - 1. Der nä chst e Satz mac ht eine Au ssa ge über die Anz a hl der erzeuge nde n Elemente. Satz 11.1 mente in

E,~

Z;.

sei p eine Prim zahl. Dann gibt es genau 1>(p - 1) erzcuqaule Ele-

B eweis: Da Z;, zyklis ch ist , gibt es mindestens ein erzeugen des Element g E Z;,. q P- I } . Das hei ßt , dass gilt : Z;' =< .'J >= {I . !J. Behaupt ung: Die erzengenden Element e von Z; sind g('ua u die z-ten Potenzen vou !J mit .'JgT(i ,p -1 ) = 1. Dips ist offensichtlich äq uivalent zur Au ssage des Sa tzes , denn die Anz ahl der v- te n Pot enzen von 9 , für die 99T(i ,1' -1 ) = 1 gilt. ist ge rade 9(1' - 1). \ Vir zei gen als erstes, dass gi für gqT(i ,1' - 1) = d > 1 kein erzeugendes Element ist . Wir setz en i = d · ;t und P - 1 = d · 1/' . Da nn ist:

tP, ... ,

Das heißt , da s Element .r/ ha t max imal d ie Ord nung 1/' < P - 1 und kann damit kein erzeugendes Element sein. Betrachten wir andererseits ein Element g i mit qqT(i ,p - 1) = 1. Mit dem erweit erten Eu klidi schen Algorit hmus findet man ga nze Zahlen n, v mit IL ·i+v· (]I - I) = 1. An genommen . !/ hätte ein e O rdnung n' < p - 1. Dann ist : (!l1l' )i." (g/l') (p-I )." = 1 und damit auch (gll't" · (g/l') {P-I j.l' = 1. Da mit folgt :

1 und

1 = (g"' )i'u . (g"' )(P - I).V = (grt') i.U+(p- l ).t' = g "'. Diese Gleichung sa gt a us, da ss 9 nur die Ordnung n' < p - 1 hät te und damit kein erzeugendes Elem ent wäre. Das ist aber ein Widerspruch Z IIf Vorausset zu ng. Also ha t .r/ die Ordnung p - 1 und d ie Behau ptung ist gezeigt. 0 Satt: 11.1 besagt. dass es in ein er zyklischen Gruppe nicht nur ein erz eugendes Element giht , sonde rn verhä ltnismä ßig viele . Xla n kennt allerdings keinen Algorithnm«. der orzcugcude Elemente konstruieren k.,·UUI. Zur Bestimmung von erzeuge nde n Elem ent en geht man daher äh nlich wie bei den P rh uzahlcu vor : Xlan wä hlt ein Elemen t zufällig a us lind tes tet , ob es sich um ein erze ugendes Ele ment ha ndelt . Es gibt effi ziente Tests . mit denen mall [entst ellen kann . ob ein Element d ie pa ssende Ordnung ha t , wobei man d azu d ie P rimfaktorzcrlegung von p - 1 braucht , vgl. Übungsaufgabe ;~, und der Sa tz l1. J sagt aus . das s ma n im Mittel nicht la uge nach e-inem erzeugend en Element suchen IIII1SS .

l lS Da s P roblem des d iskret en Logarithmus

11. 3

Da s Prob lem d es diskr e t en Logarit hmus

'1.;

Es sei P eine Primza hl, 9 ein erzeu gendes Element von und x ein e ga nze Zahl. Die Funkt ion cxp : Z _ Z;,:/, I--'> gX mo d p ht'i!i,t d isk r ete E xponentia lfunk t ion . Die Umkehrfunkt ion der diskreten Exponentialfunktion hei ßt diskre t e Logar-ith m usfu n kt .ion . \ Vl'IUI !J d u er zeugendes Element VOll Z; ist , da n n gibt es zu jedem Element aus Z; den dis kret en Logarit hmus. de nn jede Zahl aus Z; lässt sich als POtCllZ von 9 da rs tellen. Die kleinste nat ürliche Zah l :/: mit y = gX mod p heißt der diskret e Lo garit hmu s von y z u r B a si s q. Wenn 9 kein erzeugendes Element ist , d an n gibt es nicht unb edingt zu jedem y E Z; einen dls kn-tcn Logari thmus. Im folgenden setzen wir vora us , dass d u erze ugen des E lement !I VOll Z; gegeben ist. Xla n kennt bis heute keinen effizienten Algori thmus ZIlI" Best immung von diskret en Logarithmen. Die Abbildung 11.2 zeigt , da ss d ie diskret e Ex poncut ialfunkn on sich chaotis cher verh ält als ihr stetiges Pendant.

• •

• • •

•

•

-,

•

•

•

••

•

•

• •

• • •

• •

• •

•

••

•

• •

•

• •

•

•

A b b ild u ng 11. 2 Der diskrete Charme der Expo nent talfunktion

Ein naiver An sa tz zur Besti mm ung VOll d iskreten Logarit hmen ist das Ausprobioreu aHN in Frage kon n ueudcn Zahlen. Da !J ein er zeu gendes Element ist. ist d ie Ordnung von !J d ie Za hl p - 1, das bedeutet insbe sondere, da ss gP- l mo d p = rl = 1 ist , und man den dis kreten Loga rithmus einer beliebigen Za hl !J E Z; uur in der Men ge {O, . . . , P - 2} suchen IUlISS . Wen n P ein e sehr große P rimza hl ist , so ist eine solche vollständ ige Suche prakt isch undurchführba r . Ein weniger naiver Ausatz zur Berechnung VOll diskret en Log arit hmen , der deu tlich effiz ien te r als die vollständige Suche ist , ist der B aby- S t e p- G ia n t - S t epA lgor ith m us . Allerdings ist au ch dieser Algorithmus nicht effizient . Er ha t also keine polynomiclle Lau fzeit.

11 .4

D er ß aby-Step- Giallt -S t ep-A lgo ri thmu s

Oeg obcu sei eine Primzahl p und g.y E Z; , gesucht ist

loggY = :

T .

Der I3a hy-Step-Gia nt-Stt'I>-Algorith mus wählt als erstes eine Zahl t E N aus, die g riif.er als yp=1 ist . Der diskrete Loga rit hmus von y Hisst sieh da nn schreiben ab r = tl : t. + r mit 0 ::; r < 1. Diese Gleichung lässt sieh folgondcrmakeu umfor men :

u = r/

= g q.t+T {::} !J ' g - r =

q'/' /

Der Bnby-Stcp..Giant-Step-Algorithmus sucht dann zwei Zahlen rund (J mi t der Eigenschaft , dass tt : «: = g q./ gilt . Dazu werden zwei Listen angelegt:

B aby-Ste p Liste : G ia nt-Step List e:

Il ' «:

für a lle r mit 0 :::; r < t

g 'l' /

für a lle (J mit

o:::; (j < t

Nach der Berechnung der Listen sucht der Algorithmus nach einem Eintrag, der in belden Listen vorkommt. Dies er Eintrag liefert den d iskreten Logarit hmus x. Wenn man an nimmt , dass die Suche in den beiden Listen im Vergleich zu den modularen Exponen t lat ionc n vernachl ässigbar ist , dann beträgt die Komplexität d ieses Algontlnnus O ( yp=1). Dies ist zwar eine deut liche Verbesseru ng gegen.. über der vollständigen Such e, die eine Komplexität von O(p - 1) ha t, allerdings ist d ie Komplexi t ät nicht polynomicll in log p uud damit nicht effi zient . Bemerkung : Der I3aby-Step-Giant-Stcp-AlgoritlulluS ist insofern bcacht cnswert , als das s ('S sich hier tun einen so gona unten generischen Algorithmus han.. dclt . Das bedeutet, das s ('1' a uf jeder Gruppe funktion iert und nicht von de r spc»icllcn Struktur der Gruppe abhängt . Eine Variante de s Ba by-St ep..Gieut-St ep-A lgorit hmus ist der St lver-P o h ligH ellman-A lgorit hmu s : Dieser Algorithmus läs st sich anwenden , wenn (p - 1) vor allem .klciuc" P rimt eiler hat , IPH78]. Der In d e x- C a lculu s- Algo rithmus ist der effizientest e bekannte Algo rit hmus zur Beroclmung von diskreten Loga rith men. Er lässt sich al lordlngs nicht a uf jed e Gruppe anwenden. Er berechnet diskret e Logarit hmen au f zyklischen Gru ppcn und endl ichen Körpern GFÜP ). Er arbeitet da nn besonders effizient , wenn d ie P rimzahl fJ relativ ..klcin'' ist. IAd7!)] . Bis heute ist kein Algorit hmus bekannt , der effizient d iskret e Logarithmen besti mmen k ann. Da sich die d iskret e Ex ponentialfunktion effizient mit tels de s Square--and-~ IlIltiply-Algorit hm us berechnen läs st , vermutet man daher. dass es sich bei der diskreten Exponent ialfunktion um eine Einwegfunkt ion handelt: Annahm e 11. 1 (D is k reter Lo ga ri t hmus ) G(lfeben sch~n eine Primeuhl p der' Länge k Bit, ein erzeu qetulcs Element g E Z; und ein Element h nns Z; . Dann ist für- jeden effizie nten Algorithm us A die Wahrscheinlichkeit . dass C7' bei Ein.. qalsc von k , p, [I usul h den disl.;reten Logarith mus von h zur Bas is g berechnet, veriutchliissiglmr. Das heißt, d(l.~ s es fiir' jedes A eine vemachliissigbare Funktion v und ein ko E N gibt., so dass für alle k ?;: ko yilt:

11.5 Sicherheit der Diffic- Hellman-Sch lüsselver eillban mg [' [A (k , p ,!!, h) ~ a I a ER Z] :S v (k ),

Im Gegensatz zur n SA-Funkt ion gibt al funktion keine Trapdoor.

11 .5

PS

vormut lieh bei der dis kreten Ex ponenti-

Sicherhe it der Diffi e- Hellman-Sch liisse lvc rcillbarullg

Nach d iesen Vorüberleg un gen kommen wir auf d ie Difflc- Hcllman-Schlüssclvcrcinbarung zur ück. Die Sicherheit der D iffie-Helhllall -Schliisselvereillba nmg han gt eng mit dem P roblem des diskreten Logarithmus zusammen . Ein Angre ifer , der d iskrete Loga rithmen in Z; bes timmen kam !' kann offen sicht lich a uch den gemeinsamen Diffie- Hcllman-Schlüssel von A und B berechnen. Da mit müs sen die öffent lichen Pa ra met er ]J lind y also so gewä hlt werden, dass kein A ngreifer disk rete Logarit hmen zu d iesen Werten effizien t bestimm en kann . Das bed eutet zweierlei: Zum einen muss d ie Primzahl p so gl'O[~ gew ählt werden, dass es in Z;' schw ierig ist , diskrete Loga rlthmcu zu bcs tinuncu. In der P raxis wäh lt ma n heute typischer weise P rimza hlen in der Größenordnung von 204-8 Bit. Zum a nderen II ltISS man d ie Zahl y so wählen . dass sie ein e möglichst große Untergruppe von Z; erze ugt . Denn ange nommcn, g ha t n ur eine kleine Ordnung, da nn kann ein Angreifer effizient eine Ta belle der Pot en zen von ,q a nlegen . Da Z; zy klisch ist , bietet es sich an , ein erzeugendes Elem ent zu wäh len. Um die DifficHcllma n-Schlüssclverclnba ruug effizien ter zu ges talten, wählt man heut e a nstelle eines erze uge nde n Elem ent es g von Z; üblicherweise ein en Erze uger g einer Untergruppen G q von Z; mit P rimzahlord nung q . Liegt d ie P rimzah l p in der Gr ökcuordnuug VO ll 204-8 Bit , so gelten derzeit für d ie Wa hl VOll q P rim za hlen der G rökcnordnung 224- Bit als untere Grenze. Xli t dieser Pa ra motorwa hl kan n mau sicher stellen, dass kein Angreifer das geineinsa me Gehei mnis von A und B berechnen k ann , ind em er d iskret e Logarit hmen bes timm t . Ma u wd f; al lerdings bis heut e nicht , oh der Angreifer nicht au ch das Geheimnis gab mod p besti mmen kön nte, ohne d iskrete Logarithmen zu berochnen.

Die Vermut ung. dass es a uch ohne d ie Berech nung VO ll d iskreten Loga rit hmen keinen effizienten Algorithmus gibt , der den Diffie-Hcllman-Schl üsscl berech nen kan n, wird formal so formu liert :

An nahme 11.2 (Diffie- H e lhnan-A n ualun e ) Gegeben seien eine Prim zahl p der Länge k Bit, ein erzeuocndes Element g E Z; und zu_'ei Elemente rl' mod p,gb mod p. Dann ist für jeden effizienten Algorithmus A die IVahrscheinlichkcit , dass er bei Eingabe von k, p , !J,!Ja mo d p iuul gh mod p den Diffi e-HeumanSchliiseel gah mo d p berechnet , ucru achliissiqoar. Das heijit , für jedes A gibt es eme verrULchlä.%igvare Funktion l/ und ein k o E N, so da.% f ür alle I.: 2: 1.:0 gilt: P [A ( ~: , p, g, !l' mod ]I, ,( l mod p) = gilb mod p ! (l .b ER Z]::; I) ( ~: ) ,

1:18

11 Der diskrete Logar ithmu s

Man vermut et sogar no ch etwas mehr: Ein An greifer würde nicht einmal merken . dass er den korr ekten \ Vcrt err echnet hat. Dies ist d ie so gena nnte D iffte H e Ilma 11- Eilt sc beid u ngsau n a h I n e (0 i ffi e-HolIma n- Dccision-A Hil a hmc, 0 H0 Ann ahme , DDH-Allua hllle). In Z; gilt die Diffie-l lelllll 1.:0 qiit:

P [A(k , c. PI, )

~

!> (m)) S P [ll (k, P K ) ~

!>("'ll + v (k ),

1:t2 Sem an tische Sicherheit

Das bedeutet , d ass jeder Angreifer A . der a us d em öffentli chen Schlüssel und de m Geheimt ext An gaben übe r den d azu geh ör igen Kla rt ext machen kann, nur unwesentlich besser ist als ein a nderer Angre ifer B . d er de n Gehei mtex t nicht kennt. Da ein Angreifer . d er d en Geheimtex t nicht kennt , nur raten ka nn , welche Eigenscha ften ein zufä llig gewä hlter Kla rtex t hat . besi t zt d er Angreifer, d er de n Geheimtex t kennt , nu r eine u nwesent lich bes sere Erfolgswahrscheinlichkeit a ls d ie Rat ewah rscheinlichkeit . Dieses Konzep t bes chreibt et was a nderes a b d as d er Ununtcrschcid barkoit . In d iesem Spiel mu ss d er An greifer nicht herausfinden , welcher Tex t verech l üsseit worde n ist , SOlidem er soll a n Han d d es Geheimtex tes Vorhersagen über den Klart ext machen. Die Fu nkt ion h forma lisiert eine solche Vorhersago. Sie fonuaIisicrt zum Beispiel d ie Fra ge , ob ein Klartext bes timmt e Zeiche n enthält oder ein e best immte Struktur ha t. Dass eine Chiffre semantisch sieher ist , bedeu tet , d ass ein effizienter Angreifer , u nabhä ng ig d avon, ob er d en Geheimt ext kennt ode r nicht. fü r eine solche Vorhersage nur raten kann . Das heißt , d ass CI' es nicht ein mal be merken wü rd e. d as s er eine E igenschaft d es zu einem Gehei mt ext pa ssenden Klartextes rich tig geraten ha t. Der Angriff hilft ihm also nicht weit er, um Info rmat ionen über de n Klartex t zu be kommen . Geuau da s for mali siert a ber auch d ie perfekte Siche rhei t von sy mmetrische n Chiffre n. Der einzige Unterschied besteht da rin, d ass bei d er pe rfekten Siche rh eit beli ebi ge Angreifer zugelassen sind , während ma n sieh hier auf effizien te A ngreifer ein schränkt und d em An greifer a uch meh r lnfonnationcn zu r Verfügung stehen (nä mlich de r passe nd e öffent liche Schlüssel ). Bei den sy mmetrischen Chiffren wurde in Kapi tel .:1 gezeigt, d ass boid e Kouzepte äqui valent zueina nder sind. Es stellt sich d ie Fra ge, ob d ies a uch noch gilt , wenn ma n d ie Xlen gc der Angreifer auf d ie effizienten Angrei fer einschrän kt. Der folgend e Sa tz bes agt , da ss di e beiden vorgestellten Konzept e denselben Sicherheit sbcgr iff beschrei ben. Satz 13 .1 Ein Public-K ey-Kl'ypfosystem ist ye1uw (!ann polynom iell untm tenlcheidbar, wenn es semantisch eiehe r ist.

Beweis.' siehe [.:\ IRS88].

o

Dieser Sa tz bes agt s B da s Bit 0 wäh lt , so kann er das P rot okoll unve rä ndert d urchführe n, da er in diesein Fall die Q uadratwurzel nich t braucht. Verm utet er. dass B das Bit 1 wählt. so sendet er in de r Connuitmcnt-P hase den \Vel't :1:' v -I und als Response sendet er r. Die Verifikat ion geli ngt in d iesem Fa ll. de nn r 2 1:' tI ,.2, V - I. tI ( mod n] . B sollte seine Wa hl also wirklich zufä llig treffen. so dass sie für A uuvorhcrsagbar ist und d ieser Bet rug nu r mit ein er Wah rs cheinlich kcit VO ll 1/ 2 gelingt. Daher müssen A und B auch d ieses P rotokoll mehrfach d urchführen . bis B überzeugt ist. Nach t Ru nden hat A noch ein e Bet ru gs wahrs cheinlichkeit VO ll 2- t ; B ka nn a lso d urch die Anza hl der Runden das Sicherheitsniveau nach Belieben erhöhen. Dies ist ta ts ächlich ein Zero- Knowledge- Beweis für d ie Beh a uptung, A kenne ei ne Q uad ra twurzel von v mod ulo n, Dcnu kennt A wirklich eine Quadratwurzel, so kann er immer richt ig a ntwo rten. Die Eigenschaft der Durchfüh rb a rkeit ist also erfüllt . Kennt er jedoc h keine Quadratwur zel, so kan n er nicht beide möglichen Fra gen vou B (0 oder 1) bea ntwor ten . denn wenn er es dennoch könnte. so könnte er Q uadratw urzeln berechnen . denn der Q uot ient der Lekleu Autwort eu "'8/" ist eine Q uadratwurzel VO ll u. Dies ist a be r nicht möglich. den n (la. IIX den RSA-Algori t lunu s als Verschlü sselungsverfahren benutzt . wie dies in Abbildung 21.6 dargestell t ist.

269

21.1 )' IJX-Xe tze

111.\ mod n

= : CI

-c,

1112 1IIod 11 = :

c~

--2.........

1Il3 mod n = :

C3

--.S!...-

-

B

lIl~

~ ~

Abb ildu ng 21. 6 ).IIX mit (k m USA-Algorit hmus

Eine P robevers chlüsselung bedeutet h ier schli ch t das Anwend en d es öffen tli ch en Schl üssels auf d ie a usge he nde n Xa ch rich ten .

2

1n mod n

7

==

CI

C2

C3

Abbildung 2 1. 7 Probcvcrsehliisselung

E ntscheid end für di e Sicherheit eines ~ II Xes ist also d ie Vorwendung eines pro bebilis tischcn Verschlüssclu ngs vcr fahrens, vgl. Ka pit el lS. d as hei ßt , ma n IllUSS ein Verfahren verwenden, bei dem der gleiche Kla rt ext unter dem g leiche n öffentlichen Sch lüssel ste ts verschieden verschl üssel t wird .

21. 1.2

W e it er e Sicher heitsm a ßnah men

Man b raucht eine Reihe weiterer tech nischer ),Iaf,n, wobei n lind ß komplexe Zahlen sind und n:.! die Wa hrscheinlichkeit bes chreibt , mit der bei einer Xlcs sung der Zustand [0 > gemessen wird . und {32 die Wahrscheinli chkeit , dnss 11> gemessen wird.

298

2:l Quaut enk ry ptogrnfic und Quanten Comp ut ing

Wen n mau ein Syst em von zwei Qubit s be trachtet , so kan n ma ll a uch bokle una bhängig voneinander in eine Su per posit ion bringen:

(10> +li ll » EIl (10> +ßll » ~ ' 100> +ßIOl > +ßl lO > +ß'l ll > . D iese Superposition ste llt also alle vier klassischen Zus t ände .,00", .JJl" , ..Hf' und .,11" gleichzeit ig dar. Verallgem einert man d ies a uf n Qu bit s , so lassen sieh Z" Zust ände parallel zueina nde r betrachten. Die Schreibweise 100 > bedeutet hierbei. dass es sich um zwei vorsch ränkte Q u bit s ha ndelt , während d ie Schreibweise 10 > 10 > fiir zwei unabhä ngige Qubi ts st eht.

23.2.2

Q uaute ncomputer

Q ubits lassen sich aber nicht nur unabh än gig von eina nder in eine Supcrposit iOll bringen . sonde rn man kann ihre Zust ände a uch miteinander verschrän ke n. Dies kann mall sich zum Beispiel mit dem berühmten Gcdnukcnexporimcnt VOll Sch rödinger veransch aulichen: Eine Katze , eine für d ie Ka tze tödliche Chemikalie und ein radioa kti ves Atom befinden sich in einer Kiste. deren Inneres von a ußen nicht beobacht et werden kan n . Die Anordnung ist dabei SO , da ss nu r ein Zerfall des radioakt iven At om s d ie töd liche Ch em ikalie freiset zt. Da s rad ioa kti ve Ato m befindet sich. sola nge de r Zerfall nich t von a ußen bcobachtet wird . in der Superposi tion au s den Zust ändcn "nicht zerfa llen" (10 )) und .zer fall cn'' (11 » . Da mit befindet sieh a uch d ie Kat ze in eine r Superposition a us den Zust änden .Icbcndig" (1 0)) und .,tor; (1 1 )). Das C esamtsystem kann jed och nicht vier Zustände annoln ucn , sonelern nu r zwei: Den n entweder ist das Atom nicht zerfal len. und d ie Katze lebt noch , da s ents pricht de m Zust and 100 > , oder das Atom ist zerfa llen , und d ie Kat ze ist tot (1 11)). Dieses P hänom en ka nn mau a us nu t zen, 11m ma t hem at ische O pera tio nen a uf Qu bits zu simulieren : In Abhängigkeit von bisherigen Zuständen kann ma ll neue Zustä nde herbeiführen. Durch bestimmte physikalische O perationen kan n man a lso a uf einem 11Q ubit-Sysrcm mathematische Fu nk t ionen ausführen :

\\'e111l d ie Q ubit s verschrä nkt si nd . k ann ma n a uf ihnen gleichzeitig und parallel zueinander Funktionen berechnen . Dies ist ein großer Vort eil gegenü be r klassischen Rech nern. d ie in einein Schritt stets nur eine Ei nga be ma nipulieren können . Xlau kann zeigen. dass sich al le ma themat ischen O pera t ionen. d ie man mit ei ner Turing-Maschi ne durchführen kann . auch mi t einem Quantencom put er herechnen las sen . Zusa mmen mit der parallelen Ausfüh rbarkeit von Funktionell a uf vers chrä nkten Qubits werden Q ua ntenco m puter da mit zu einem l ns t ruu ient , das nicht nu r a lle A ufgabe n eine r Turing-Xlaschinc bewä ltigen kann , sondern das d iese auch noch deut lich effizient er durchfüh ren kann .

2 ;~.2

Quanten C ompu tin g

299

Eine mathematisch e Fu n ktion ist für Qubits so wicht ig , dass sie hier ausdrücklieh erwä hnt werden so ll: d ie Quant ell-Fourier-TI·ullsforma tion . QUCl ntonmechanisch Hiss t sie sich folgendennaßen b esch rei ben: Fü r a lle 0 :::; x < '1 = 2" ist '1-1

1 """'"'

1:1:>-- l'72 L )e>·e 21riq rc • '1

c= ü

Am de utlichsten erkennt man den E ffizienzvort eil der Q ua ntencomput er am Beispi el d er Fa ktonsicruug. bei dem auch d ie Fourier- T ra nsform a ti on zum E insa t z kommt. Au f einer Turi ng-M aschine kan n man E xp onent iat ionen nur nacheinander a us fü h ren. DeI" folgende Abschnit t zeigt. d ass mall mi t ei nem Qu an tencomput er viele Exponentt a t ionen g leichzeit ig berochneu kann. Dadurch wird d ie Fa ktort sierung ga nzer Za hlen a uf einem Quantencomput er zu einem effizient zu lösende n

P rob lein.

23 .2 .3

Faktor- lsle rung mi t Quant e n comput eru

Das wicht igs te Beis p iel fü r d ie Bedeut u ng der Quantencomputer st ammt VO ll P. Shor. [Sh !)4]. EI' konnt e lUD4 zeigen , wie sich ein Quant encomputer zur Lösu ng des Fakto risiorungsproblcms benu t zen läs st . Der Algori thm us ge ht d abei fü r ein e gegebene ganze Za hl 11. folg eudennaken vo r: Er sucht zwei Zahlen x u nd s m it den folgenden Eigen sch aften:

es 1 (m od n) und

.1'2$

r" =1=- 1 (m odn ). Dan n kann man n faktorisiere n , denn es gilt ;[.28 - 1 es 0 (mod n), also folgt ( X"~ + 1) (:r~ - 1) == 0 (m od 1/). Die Zahl 1/ ist d aher ei n Teil er d es P rod u ktes. wegen der zweiten geford er ten Eigenschaft teilt 11. a ber keinen der beiden Fa ktoren . Mittels d es Euklidischen Algorithmus kann man n da mit faktorisicrcn. Um so lche Zahlenc und .'I zu finden . wird eine beliebige ga nze Zahl .1: aus Z;' gewählt. Im Folgenden b ezeichnet r d ie O rdnung von .1:, d ie all erdings unbekannt is t. Als ers tes bes tim mt m an zwei ganze Zahlen '1 und (/ m it der Eigenschaft 2 :::; q < 21/. 2 , wobei q = 2'/ gilt. Dann initialisiert m an ei n Syste m mit zwei 11. Qubit-Rcgistcm der Läng e '1'. Die Eint rä ge d es ersten Registers si nd un abhängig vo neinander, wa hrend di e E int räge des zweiten Regi st ers mit d en jeweilig entsprcehenden Ei n trägen des ersten Regis ters ver schränkt sind . Zu nä ch st b ringt m an d as ers te Regis ter in eine Su p er p osi tion VO ll allen Zahlen O :::; a < q:

1 q-I 1/2

'1

I: In> 10 > . Il =O

Da n n b erechnet man im zweiten Reg is ter fü r a lle Eint rä ge di e c-tc P otenz

VO ll .1':

:lOO

2:l Quautenk ry ptogrnfic lind Qu anten Co mp ut ing

1

q- l

17'2 L: la> I:r" mod n> . q

a=O

Im letzten Schritt wendet mau die Fouri er-Tran sfonna tion Huf das erste Registe r an:

!L

L (~ l"-~" C je> I:r" mod n.> .

q-I q - I

fJ

a =ü c= ()

Schli eßlich m isst mau den Zusta nd in beiden Reg istern . Xli t der Messun g geh t n at ürlich di e Su perposition d er Zust ände in den einzel nen Regist ereinträgen ver loren . Die Fra gen . d ie sich dami t stellen. lauten : \Velche!' Zust and besitzt bei d iese r Xles s un g di e größte Wahrscheinlichkeit , und welch e R ückschlüsse kann ma n

d araus ziehen? Wir besch äftigen U Il S zunächst m it d er ersten Frage . Daz u best immen wir di e Wa hrscheinlichkeit für den Zustand [c> l;l,k mod n > . Diese Wahr scheinlich keit. ka nu ma n berechnen d ur ch 2

P (lc» =

q- l

1

L

q

2 .. ;,,~

e •

(I = {) XII

es x k'

1110 (111

Um diesen Aus druck zu vereinfachen, ers etzen wir zwa r unbeka nnt , d en noch wis sen wir, das s es

Cl

+ k, Die Zahl r ist ei ne ga nze Zahl b m it d er

durch br

gCllIHi

gcwtinschten Eigen scha ft gibt. Da mit kan n man umformen: 1

P (lc » =

~ ~

fJ

2

19- 1- kJ e

2,,.;(brtOc q

b= O

Der Exponentialtenn lässt sieh d enn wie folgt vereinfachen: 2

wob ei [rc], eint' Ab kü rzun g für rc mod q ist.

Man kann leicht nach rechnen . dass diese Sunuuc maximal wird, falls folgende Unglck-hn ng erfüllt ist :

r

r

- -2 < -. - [rc] 'i < - 2 Anders form ulier t heißt da s . das s derjenige Zus tand [c > die größt e Wah rscheinlich kcit hat , gemessen zu werden . für den es e-in d gibt mi t;

2 ;~"2

Quanten C ompu tin g

:lOl r

--2 < -

rr: - d(!

1"

< -. - 2

Dies ist äquiva len t zu der Forderung, das s es eine rationale Zahl dI r gibt mit 11 und

,.
. für den es eine ra t ionale Zah l dl" gibt. so das s r < TI. und

gilt . Dies e rat iona le Zahl kann man berechnen . wod urch ma n die Ordnung r der Zahl :r gefunden ha t. Wenn die Zahl r gerade ist , dann kann man mit dem Euklidischen Algorithmus aus (:rr f 2 - 1) und 11 ein en der P rim fa ktore n von 11 besti mmen. Der Erfolg des Algorithmus hängt a lso davon a b. ob mall den richtigen Zust a nd misst lind ob die Zah l r eine gerade Ord nung ha t. Xla n kann zeigen , dass beides mit hinreichend hohcr \Vah rsdwinlichkeit a uft ritt , um den Algo rit hmus nich t allzu oft durchführen zu müssen . Der Algorithmus VO ll Sho r war das erste Beispiel für da s enorme Potent ia l der Quantencomput er. ShO!" konnte a ußerdem zeigen , dass die Faktorisierung nicht das einz ige ma th em atische P roble m ist , da s sich mit Q ua ntencom putern effizient lösen lässt : Auch da s P robk-m des diskreten Logari thmus lässt sich mit ei nem ähnlichen Algori t hmus effizient lösen .

23 .2 .4

A u swir ku n gen a u f d ie Kryptografie

Shors Quantenalgorit hmus zur Fa ktorisicnmg ga nzer Zahlen zeigt , (lass die Entwicklung von Q uantencomputern eine n erheblichen Einfluss auf die Kryptografie ha ben wird" P ra ktisch alle heute eingesetzten Algori thmen der Pub lic- K cyKryptogra fie kön nen nicht mehr a ls sicher gelt en, wenn Qu antencomputer rechnisch rea lisier t werden können . Bis heute ist unklar, ob es sich hier um ein g runds ätzliches P hä nomen haudclt. a lso P ublic-Key-K ryptografi e pr inz ipiell nicht mehr m öglich ist , wenn es Quantencomput er gibt . Es lässt sich a be r zeigen. dass die Auswirk ungen a uf die symmetrische Krv ptografl e weniger grav ierend sind. Da..selldozu fa llsgeueratol'. 125 HSA-Sigua t ur. 168, 169. 185 Hun-Test , 54

Pscudozufall szahl , 52. 12f, Pseudozufallsae hlenfolge. 55 , 100

S-I3ox, 75, 76 Sj)' IL\IE , 289 Sa t z von E uler, 116. 121. 1:J:! Sa tz von Fernt at - kleiner , 1 2 :~ Schachgrokmeistorangriff , 2:iO, 2:i4 Sd üelleregistN, 55 Schlüssel, 3, 2:1 Schlüsseletablierung . 217, 228. 2:1-4. 2:lG Schiiisseletablicrungsprot oko ll. 228 Schlüsselra um . H9 Sch lüss elt ransport protokoll. 228, 2:14. 2:16.

222

Public Key Hing, 288 Public- Key-E igen schaft , G. 107 Puhlic-Key-I nfra st ruk t ureu, 211 Public-Koy- Kryptogr afie , 4, 105 Public-Kcy- Kryp tosystem. 105 Public-Kcy-Sign a turschcma , 167

Public-Key-Verschlfisselungsvorfahren , l OG, 107, 159, zn . 2:10. 2GB Publtc-Key-Zcrt tt ikat v zl z

Quad ra t ischer Xtcht res t , 152, 197 Quad ratischer Hes t , 152, 197, 201 , 205 quadra t isches Sieh, 118 Quanten Comput tng , 296 Quanteu-Fourier-Transformat Ion, 2!J!) Quantenbit . 297 Que utcnk aual , 29:1 O ue nten kry pt ogra ftc, 29:J Qubit , 29 7 I(ückfl.( lresse - anonyme , 268 R ück kop pluugsfuu kt ion. Bö Rückkcp pluugspo lyn om. Bs Hik kru fiist e . 2 14 Ra hin -Signa t ur , 154 Ha bin, Verschlüssclungsvcrfahn-u , 153 Ra ndom-Or acle..)'lol ld l, 186 Rechuerjscher Zcro- Know ledge- Beweis , 20:~ Record- Layer- P ro tokol l. 279

2. 0 Schlüsse!veI"e illbaru llgspro tokoll, 228, 240 Sch lüsselverwalt u ng. 207, 287 Schrö d iugers Kat ze, 298 Schwach kollisionsn-sist cn t , 177 Schwelleus che ma. 25:1. 254 Secret-Sharing-Verfe hre u. 252 Secu re Sockets Luyer , 278 Selbst sy nchronis ierend. 9fi. 98 - 100 Selec tive forge ry, IG8 Selektives F älsche n. I G8 Semantisch siche r, 1m , Hi3 Somant ische Sicher heit , 28, HiO, Hi2, Hi4 Scndcrano nyuntät , 265 Scr tennnnnner, 22:1 Server , 278 Sess ion key, 94, 228 S HA- I- Algor it h mns , 184 . 19;1. 287 Shift How, 8:1, 86 Sho r-Algorit hmus, 2!)9

Index Shottest. vcctor probletu. 157 Shrtuking- Ccuerator, {)2. 64 Sicher im Sinne der polynomlellen U nunterscheidbarkclr , 49 Sicher im Sinlle der Ununtors cheidbarkcit , 28, 4 1

Sicherheit - perfekt , 28 - perfekte. 28 - semant ische, 28 , lGO. 1{)2 Siclu-rhcitsalgoritlunuaD Sichcrhcitxdleust vIl Sichcrhci ts mechauis mus, 9 Sicherheitsparameter. 5a. 20 1 Signa t ur, 221 , 224 , 270 , 279 , 287 - beweisbar sichere, 170 , 187 - blinde , 2{)5 , 270 - d igita le, 167 , 176 , 185 Stgna t ur algor lt luuus, )67 Signa t ur verfa hren. ) W ) , 222 , zn. zso. 27 1 SilV('r-Poh lig-Hellmall-Al gorit hmus. l :lG Simulation. 1%. 20Z. 204 Sing ulä r, 146 Sitaungsschlilssol , 94 , 228 , 2:14. 2:lG, 2:18, 240 Soundness, 201

Sprache, 201 Sq uaro- and-Xlultiply-Algo rit lnuus, 119 SSL, I!J:l, 278 St ark kollisiousn-sistent , 177 st a rke Primza hl. 118 st a rke HS A-Alilla h llle, 128 St at ist ischer Test , 5:t 54 St at ist ischer Zero-Kuowlcd ge-Bewels. 20:1 Stegauogre fic, 9 Stromcluttre, ;I!. \):1 St romoricnt tcrt, \):1. 9rl, 97 Subß yt es . 8:1. 85 , 87 Substitution . 14 Substit utionsbox. 75 Summationsgenerator. (i2 Su perposit ion, 29 7 Symmctrischo Kryptografie , 10r) Sy nchron, 98 , 100 Sy nchronis a tion, 2:18

TAX. 219 'Icilucluucra ut hcutifikat jon, 216 , 228

'Ieilnchmcra ut hentixit iit., 2. 8 Tciluehmcridcntifikation, 21 G Thres hcld-Sigua turverfuhren , 257 T hreshold-Verfa hren .25:1 Ttmc-Mcmory-Tradcoft. fi9 T:\ I:\-Protokoll, 2:18, 245 Total break, HiS Transakt ious uumnicrv älü Tr ansposition. 13 Trapdoor-Einwegfunktion. 112 , 128 Triple-DES-Algorit hmlls, 182 ,286 Trust Center, 212 'I'rustrd third party, 229 TT P, 229 . 2:J4 'Iu r tng- xtesclune, 4~ , 200. 299 Two- Key-Triple-DES, 92 Unülx-rtragbarkeit , 217, 218, 22:1 Uuebhäu gigkett. :la Unbedingt e Sicherheit , 45 Un cigcutltchcr P unk t , 1--18 Unendlich ferner Punkt , 1-18 Unerhebliche Funktion . 29 Universal forgrry, HiS Universell fälschbar. I G9 Universelle Falschba rkeit , l {i8 Ununterschcidbarkcit , 49 - polyuomielle, HiO, IG1

Verbindlichkeit , 2. toB -1 11, 279 Vorfügbarkcit., 9, 244 Verifier, 200 , 216 Veri fikat ion, 198 , 199 Ver ifikationsa lgorithmus. lß7 Veruachliissigbar c Funkt ion . 29 , 20 1 Vcrnaiu-Clnffro. :m Versc hiebechiffre . l :t :J--1. 35 Versc hlüs selung. 2:1, 221. 27!J - probab ilisti schc, IG2 Verschlüsseluugsfun ktion. 2:1 Vcrschlüs seluu gsverfe hrcn . 2:1, 220 , 221. 244 , 280 proba billstlsches. 2mJ Vel'schrällku llg. 2!J8 Ver t ra ulichkeit , 2. 22. IO!J, 111, 279, 2K6 Viclfachsuuuneudarst elluug. 120, 121 Vigcm-re-C hi ffre, 15, :In Vollständige Schliissclsuehe, I:J

-

Ind ex Vollst a ud ige Suche, 67 Vorhersagbarkelt vou liucaren Schieben-gist erfcl gen, 62 Vorper lode . 54 Vor tei l. 2n \Yör terblld mtta, ke, 2 1H \\'a hk ll - elektronische , 276 \ Vahrscheinlichkeit - a postrriori. :t1 - a priori. :12 Web of Tr ust. 289 \\'('chsc lcode-Vcrfahn'll, 217, 2 19, 221, 225 \\'pch se!m dl'- Verfahn-uiuit geheimem Sch liisscl. 220 \ Vechsek odc- Verfahren m it Passwor t , 220 \\'('rtet abelle, G8, 70 wesentlich verschieden. 20!) witness, 20--1 Wi t uess indistinguishahle, 20fl witncss-Hldtng-P rotokotlv äü.t Wnrld Wide W(,b. 278 \Vorst -casp-L allfzeit , 46 Wort , 2:1. 201 Zähler, 220 Zahlk örp ersleb. 118 Zeichen, 2:J Zeit atempul, 189, 220,22:1, zu . 2--12 Zeitstompeldienst. , 21--1 Zero Knowk-dgc Proofs of Knowh-dge , 201,

20' Zero Knowk-dgu Proofs of Xlemberslup , 201 Zcro-Kuowlcdgc- Bcweis, 195, 217, 22:1. 225 - perfekter, 202 , 20:1 - rcc hncrtscher. 20:J - st a tist ischer, 20:1 Zel"O-l( lIowlt,dg('- EigeIlSd lll.ft , 196. 198, 200, 202.20--1 Zer tifikat , 22:t 225, 2:10, 2:n , 240, 27G, 281. 289 Zortt nztcrungslnstenz . 2 12. 22:J, 276 Zeuge, 20-1 Znfallsbaud , 201 Zugangsko nt rolle, 2 17 Zyklus, 5--1