Cryptography Reference
In-Depth Information
Satz 6.3.14 (Primzahlsatz).
Es gilt
n
ln
n
+2
<π
(
n
)
<
n
ln
n
für
n ≥
55
.
−
4
Aus diesem Satz erhalten wir sofort:
Folgerung 6.3.4.
Es gilt
2
l
Prob
{
n
ist prim
}≥
für
l
≥
44
,
(6.3.12)
wobei
n
eine Zufallsvariable bezeichnet, die zufällig, gleichverteilt eine ungerade natürli-
che Zahl in
2
l−
1
+1
,...,
2
l
{
−
1
}
liefert, also eine Zahl mit einer Binärdarstellung der
l−
2
.
Form
1
u
1
für ein
u
∈{
0
,
1
}
Beweis.
Es gilt:
=
π
(2
l
)
−
π
(2
l−
1
)
2
l−
2
Prob
{
n
ist prim
}
ln(2
l
)+2
−
2
l−
1
2
l
(1)
≥
ln(2
l−
1
)
−
4
2
l−
2
4
ln(2
l
)+2
−
2
ln(2
l−
1
)
−
4
=
4
L
+2
−
2
=
,
L
−
c
wobei (
1
) aus Satz 6.3.14 folgt und wir
L
=ln(2
l
)
(
=
l
ln 2
)und
c
=ln(2)+4
setzen.
Um (6.3.12) zu zeigen, suchen wir eine hinreichende Bedingung dafür, dass der letzte
Ausdruck
·
≥
2ln(2)
/L
ist. Wenn wir
d
für
ln(2)
schreiben, ist dies äquivalent zu
4
·
(
L
−
c
)
·
L
−
2
·
(
L
+2)
·
L
−
2
·
d
·
(
L
+2)
·
(
L
−
c
)
≥
0
,
was wiederum äquivalent ist zu
(2
−
2
d
)
· L
2
−
(4
c
+4
−
2
dc
+4
d
)
·
L
+4
dc
≥
0
.
Hinreichend dafür ist, wie man leicht nachrechnet,
L
≥
30
,
33
, und damit
l
≥
44
.
6.4
RSA
Das erste asymmetrische Kryptoschema wurde, wie bereits erwähnt, von Ron Rivest,
Adi Shamir und Len Adleman 1978 vorgeschlagen und ist unter dem Namen »RSA«
bekannt. Es spielt auch heute noch eine wichtige Rolle in der Praxis. Im Folgenden
werden wir zunächst das RSA-Kryptoschema einführen und anschließend seine Sicherheit
diskutieren.
