Beweisarchiv: Kryptografie
- Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit
- Kryptosysteme: Korrektheit des RSA-Kryptosystems · Sicherheit des GMR-Signatursystems
- Pseudozufall: Sicherheit des s²-mod-n-Generators
Das GMR-Signatursystem nutzt kollisionsfreie Falltür-Einwegpermutationen. Zur Erklärung siehe dazu Falltür-Einwegfunktionen (engl. trapdoor one-way function). Diese haben den Vorteil, dass sie sich nur mit Kenntnis eines Geheimnisses effizient umkehren lassen. Es wird also die Umkehrpermutation mit Kenntnis des Geheimnisses zum Signieren einer Nachricht verwendet und die Signatur dann ohne Kenntnis des Geheimnisses mit der Permutation überprüft.
Als Geheimnis verwendet man zwei große Primfaktoren von
. Dabei ist
öffentlich, da es zum Testen benötigt wird.
Es existiert eine kollisionsfreie Falltür-Einwegpermutation.
Dazu zeigen wir im Teil 1, dass die im Folgenden vorgeschlagene Permutation eine Falltür-Einwegpermutation ist. Im Teil 2 wird bewiesen, dass es mindestens so schwer ist, eine Kollision zu finden, wie
zu faktorisieren. Das ist nützlich, da das Faktorisierungsproblem für eine beliebige ganze Zahl als nicht mit polynomialem Zeitaufwand lösbar gilt.
Sei
(
ist das Jacobi-Symbol)
der Definitionsbereich für folgende Permutation:
![{\displaystyle {\begin{aligned}f_{0}(x)&={\begin{cases}x^{2}{\pmod {n}}\ ,&{\text{wenn }}x^{2}\in D_{n}\ ,\\-x^{2}{\pmod {n}}&{\text{sonst}}\ ,\end{cases}}\\f_{1}(x)&={\begin{cases}4x^{2}{\pmod {n}}\ ,&{\text{wenn }}4x^{2}\in D_{n}\ ,\\-4x^{2}{\pmod {n}}&{\text{sonst}}\ .\end{cases}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04b2ede78aa8ca1b6e26d8bc308513187071193d)
Die beiden folgenden Permutationen dienen dem Signieren der Zeichen „1” und „0” an einer zufällig gewählten Referenz
. Die Umkehrfunktionen benötigen Wurzelziehen in
, was nur mit Kenntnis der beiden Primfaktoren effizient möglich ist. Siehe dazu: Wurzelziehen ist schwer
![{\displaystyle {\begin{aligned}f_{0}^{-1}(x)&={\begin{cases}{\sqrt {x}}{\pmod {n}}\ ,&{\text{wenn }}{\sqrt {x}}\in D_{n}\ ,\\-{\sqrt {x}}{\pmod {n}}&{\text{sonst}}\ ,\end{cases}}\\f_{1}^{-1}(x)&={\begin{cases}2^{-1}{\sqrt {x}}{\pmod {n}}\ ,&{\text{wenn }}2^{-1}{\sqrt {x}}\in D_{n}\ ,\\-2^{-1}{\sqrt {x}}{\pmod {n}}&{\text{sonst}}\ .\end{cases}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0adab2dbcb28981ff51d97228ab72279c6a1af14)
Weiterhin sei
.
Da wir dies im Beweis mehrfach verwenden, sei hier schon einmal darauf hingewiesen, dass damit gilt:
(-1 ist kein quadratischer Rest modulo
)
![{\displaystyle 2\notin QR_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a00dc9aea43a8e40148ec15d0d07812cdff86b31)
Wir zeigen nun, dass es sich bei
tatsächlich um eine Permutation handelt, indem wir beweisen, dass folgende Implikation gilt:
![{\displaystyle f_{0}(x)=f_{0}(y)\quad \Rightarrow \quad x=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfed606cecccbacde3a582c3616f997b90c8b5d8)
Sei
![{\displaystyle \Rightarrow x^{2}\equiv y^{2}{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f74a2ef56b46af766a40ce2d2d668cf0bd99684f)
Es ist
da
, aber
und damit auch
.
![{\displaystyle x^{2}\equiv y^{2}{\pmod {n}}\quad \Rightarrow x\equiv \pm y{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04ae00ad25d44f49644545d2560f9431de20ceee)
Wegen
.
![{\displaystyle \Rightarrow \quad x=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bffaba840418b0b913430ea075e1dc81b57da8c6)
Jetzt folgt noch der Beweis für
:
Sei
![{\displaystyle \Rightarrow \quad 4x^{2}\equiv 4y^{2}{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/332d8187ad99d50cc144120225997cefe3e59c75)
![{\displaystyle \Rightarrow \quad x^{2}\equiv y^{2}{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea9c4f4607d327b882c2abb011c45870533881c1)
und ![{\displaystyle x,\ y\in D_{n}:0<x,\ y<{\frac {n}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/072309af5527816bed66c557469405726bde7c7d)
![{\displaystyle \Rightarrow \quad x=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bffaba840418b0b913430ea075e1dc81b57da8c6)
Im zweiten Teil des Beweises zeigen wir, dass die gefundenen Permutationen kollisionsresistent sind. Dazu zeigen wir die Implikation „Kollisionen finden ist leicht”
„Faktorisieren ist leicht.”
Angenommen, es existieren
,
, für die es eine Kollision gibt:
![{\displaystyle f_{0}(x)=f_{1}(y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/125f6e07c2aa3a54d9ce26f21251c3a32959ab34)
![{\displaystyle \Rightarrow \quad x^{2}\equiv 4y^{2}{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5855f9c4a81e7914c263d7e50478c664d712d9e)
Es ist
da
, aber
und damit auch
.
![{\displaystyle {\begin{aligned}x^{2}\equiv 4y^{2}{\pmod {n}}\quad \Rightarrow \quad x^{2}-4y^{2}&\equiv 0{\pmod {n}}\\(x+2y)\cdot (x-2y)&\equiv 0{\pmod {n}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cecbea0568de09746526cec72a76bbfe7cf163b)
![{\displaystyle (1)\qquad \Rightarrow \quad n\mid (x+2y)\cdot (x-2y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39637bb019f2499a0624237e472dc4b8788b148b)
, aber ![{\displaystyle \left({\frac {\pm 2y}{n}}\right)=-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dadadea6161090897e7db623bf1ef11d5d872ea4)
![{\displaystyle \Rightarrow \quad x\not \equiv \pm 2y{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f14dd19e14f64eb90d89cd3413adfa83b2b9239)
![{\displaystyle (2)\qquad \Rightarrow \quad n\nmid x\pm 2y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99234e6a1dbc71652366e0f2bade7f3f8bd9e7a7)
Wegen
und
muss
einen der beiden Primfaktoren enthalten. Damit ist
![{\displaystyle {\text{ggT}}(x-2y,\ n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6c42194f7e64a544958f04a233188707f65a112)
einer der beiden Primfaktoren von
Also gilt: „Kollisionen finden ist leicht.”
„Faktorisieren ist leicht.”
GMR (Signaturverfahren)
Falltür-Einwegfunktion
Faktorisierungsverfahren
Polynomialzeit
Quadratischer Rest
Jacobi-Symbol
Beweisarchiv: Kryptografie
- Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit
- Kryptosysteme: Korrektheit des RSA-Kryptosystems · Sicherheit des GMR-Signatursystems
- Pseudozufall: Sicherheit des s²-mod-n-Generators