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