Cryptography Reference
In-Depth Information
The value of
t
is kept private. Note that only A should be able to calculate
t
, as only he
knows the prime factors of
n
.
2.
A chooses a random positive integer
r
less than
n
, and sends to B (the challenger) two
values:
2
modulo
n
, and
z
2
= lnr of
sz
1
modulo
n
,
z
1
= lnr of
r
z
1
is an inverse of
z
1
modulo
n
where
.
3.
z
1
z
2
s
n
c
c
B checks that
modulo
. He then randomly chooses either
= 0 or
= 1 and sends
c
to A.
4.
A will respond in one of two ways:
• If
c
= 0, A sends the message
r
to B.
• If
c
= 1, A sends the lnr of
tr
modulo
n
, where
r
is an inverse of
r
modulo
n
.
2
modulo
n
, and does one of two things:
5.
B now computes the lnr of
m
• If
c
= 0, he checks that
r
2
z
1
(mod
m
).
2
• If
c
= 1, he checks that (
tr
)
2
=
t
2
r
sz
1
z
2
(mod
n
).
After this process, B knows that A can compute
t
, a square root of
s
modulo
n
, but he can-
not compute
t
himself, and
t
is never revealed to him. These are the only values that B knows
2
,
2
,
2
)
(modulo
n
):
z
1
r
z
2
s
(
r
sr
s
, and exactly one of
r
or
tr
. Note that B can never
be given both
r
and
tr
, for this allows him to calculate
t
. This process can be repeated as
often as necessary with different random values for
r
until B is convinced that A knows
t
.
However, it is absolutely vital that A choose a different value for
r
every time. Why?
E
XAMPLE
.
Suppose A is using the public modulus
n
=
274767815982245548988790206801956651309342982830065216921948667831130363
270253391613297772360579492679629996501029139838682116550051160900059917
252079335683044082645443287136361829237904549448424168235143278727967298
537931735369900497614908459888542386548176723918689759709749816846741951
438624571462267660236650416857894422109721140233441189969425961870588371
894903496708435357401553646260714625504652954935134556139340783655294871
737383374223242600468713011439066059016281996201542058384927054227873607
471972731775123706246506154077712330891353812432890865488929521246586593
80550940695643273559171683514261677617772051153
which is the product of two large, strong (and private) primes congruent to 3 modulo 4;
namely,
p
=
200766270232954088077041575959108612757411238838003505144742064111712514
438539012193632244782163192814569872158475903654023762579506771732582156
Search WWH ::
Custom Search