Upload
johan-reichstein
View
114
Download
0
Embed Size (px)
Citation preview
Bit Commitment mit quadratischen Resten
Vortrag von
Josef Pozny
8.7.2008
Ausblick
Quadratische Reste modulo einer Primzahl pQuadratische Reste modulo NBit Commitment mit quadratischen Resten
Quadratische Reste modulo einer Primzahl p
Definition:
2
*p
p
Sei y . Dann ist y ein quadratischer Rest modulo p,
wenn es ein x gibt, mit x ymodp.
Z
Z
*p pQR : y | y ist quadratischer RestZ
*p pQNR : y | y ist quadratischer NichtrestZ
Quadratische Reste modulo einer Primzahl p
Proposition:2
*p
Sei p eine Primzahl. Dann hat jeder quadratische
Rest in genau zwei Quadratwurzeln.Z
Quadratische Reste modulo einer Primzahl p
Proposition:2
*p
Sei p eine Primzahl. Dann hat jeder quadratische
Rest in genau zwei Quadratwurzeln.Z
12 2
*p
p pp
QR QNRZ
Folgerung:
Quadratische Reste modulo einer Primzahl p
Definition:
*p
p
Sei p 2 eine Primzahl und x . Das Jacobi-Symbol
(x) von x modulo p
Z
1
1
p, wenn x ein quadratischer Rest modulo p ist
(x) :, wenn x kein quadratischer Rest modulo p ist
Quadratische Reste modulo einer Primzahl p
ist eine zyklische Gruppe der Ordnung . *pZ 1p
Quadratische Reste modulo einer Primzahl p
ist eine zyklische Gruppe der Ordnung .
*pZ 1p
1 1 11 10 1 2 12 2 2
p p p* pp g ,g ,g ,...,g ,g ,g ,...,gZ
*pErzeuger g von Z
Quadratische Reste modulo einer Primzahl p
ist eine zyklische Gruppe der Ordnung .
Quadrieren liefert:
*pZ 1p
1 1 11 10 1 2 12 2 2
p p p* pp g ,g ,g ,...,g ,g ,g ,...,gZ
*pErzeuger g von Z
0 2 4 3 1 1 2 4p p p ppQR g ,g ,g ,...,g ,g ,g ,...,g
Quadratische Reste modulo einer Primzahl p
Kleiner Satz von Fermat:
1 1 * ppSei p eine Primzahl und x . Dann ist x modp.Z
Quadratische Reste modulo einer Primzahl p
Kleiner Satz von Fermat:
0 2 4 3 0 2 3p ppQR g ,g ,g ,...,g ,g ,g ,...,g
1 1 * ppSei p eine Primzahl und x . Dann ist x modp.Z
Anwenden dieses Satzes führt auf:
D.h. die quadratischen Reste lassen sich darstellen als , wobei gerade ist.
jg
j
Quadratische Reste modulo einer Primzahl p
Proposition:2Sei p eine Primzahl. Dann gilt
12
p
p(x) x modp
Quadratische Reste modulo einer Primzahl p
Proposition:
Algorithmus 1:
1.Setze .
2.Falls , dann gebe aus +1.
3.Sonst gebe aus -1.
2Sei p eine Primzahl. Dann gilt12
p
p(x) x modp
12
p
a : x modp
1a
Quadratische Reste modulo N
Sei , wobei zwei Primzahlen größer als 2 sind.Betrachte nun den Raum .
N pq p,q*NZ
Quadratische Reste modulo N
Sei , wobei zwei Primzahlen größer als 2 sind.Betrachte nun den Raum .Der Chinesische Restsatz liefert einen Isomorphismus
N pq p,q*NZ
* * *N p qZ Z Z
p qy y ,y
Quadratische Reste modulo N
Proposition:
*N p q
Seien p,q Primzahlen mit p q und sei N pq.
Sei y mit y y ,y .Z
1 1 p p q q
Dann ist y ein quadratischer Rest modulo N genau dann,
wenn (y ) und (y ) .
Quadratische Reste modulo N
N p p q q(y) : (y ) (y )
Quadratische Reste modulo N
bedeutet nicht dass y ein quadratischer Rest ist. Denn es kann gelten.
N p p q q(y) : (y ) (y )
1 N(y)1 p p q q(y ) (y )
Quadratische Reste modulo N
bedeutet nicht dass y ein quadratischer Rest ist. Denn es kann gelten.Faktorisierung bekannt, dann prüfe mit Algorithmus 1, ob und gilt.
N p p q q(y) : (y ) (y )
1 N(y)1 p p q q(y ) (y )
N pq1 q q(y ) 1 p p(y )
Quadratische Reste modulo N
bedeutet nicht dass y ein quadratischer Rest ist. Denn es kann gelten.Faktorisierung bekannt, dann prüfe mit Algorithmus 1, ob und gilt.Zerlegung unbekannt, dann ist es praktisch unmöglich quadratischen Rest von Nichtrest zu unterscheiden.
N p p q q(y) : (y ) (y )
1 N(y)1 p p q q(y ) (y )
N pq1 q q(y ) 1 p p(y )
Quadratische Reste modulo N
Quadratische-Reste-Annahme:
Dann ist es für jemanden, der die Zerlegung nicht kennt, praktisch unmöglich zu entscheiden, ob ein quadratischer Rest modulo ist, oder nicht.
1 *N NSei N pq, und x mit (x) .Z
N pqx
N
Bit Commitment mit quadratischen Resten
Bit Commitment mit quadratischen Resten
1 *N NSei N pq, und x mit (x) . Seien N und x
öffentlich.
Z
Bit Commitment mit quadratischen Resten
Festlegung:
1. Alice wählt ein Bit .
2. Sie wählt zufällig ein .
3. Sie verschlüsselt das Bit durch , und gibt
an Bob.
1 *N NSei N pq, und x mit (x) . Seien N und x
öffentlich.
Z
0 1b ,
*Nr Z
2bc x r modN c
Bit Commitment mit quadratischen Resten
Offenlegung:
1. Alice sendet b und r an Bob.
2. Bob rechnet nach, ob stimmt.2bc x r modN
Bit Commitment mit quadratischen Resten
Aufgrund der Quadratische-Reste-Annahme, kann Bob nicht entscheiden, ob c ein quadratischer Rest ist, oder nicht.
Durch die Kenntnis von c, erhält Bob also keine Information über b.
Bit Commitment mit quadratischen Resten
Sobald c übergeben wurde, lässt sich das Commitment nicht mehr ändern.
Denn andernfalls müsste es und geben, so dass
gilt.
1r
1 2 0 21 2 x r modN c x r modN
2r
Bit Commitment mit quadratischen Resten
Sobald c übergeben wurde, lässt sich das Commitment nicht mehr ändern.
Denn andernfalls müsste es und geben, so dass
gilt.
Daraus folgt aber
was der Wahl von als quadratischer Nichtrest widerspricht.
1r
1 2 0 21 2 x r modN c x r modN
2r
22 2 11 2 2 1
x r r modN x r r modN,
x