Cryptography Reference
In-Depth Information
5.20. Blum integers and their properties are examined in Appendix B on pages
507 and 508. There is a coin flipping scheme based on Blum integers that
we now describe.
1. Bob generates a Blum integer
n
, a random
x
∈
N
relatively prime to
x
2
(mod
n
) and
x
1
≡
x
0
(mod
n
). He sends
n
n
, and computes
x
0
≡
and
x
1
to Alice.
2. Alice guesses the parity of
x
and sends the guess to Bob.
3. Bob sends
x
and
x
0
to Alice.
4. Alice checks that both
x
0
≡
x
2
(mod
n
) and
x
1
≡
x
0
(mod
n
). Thus,
Alice can determine if the guess is correct.
Explain how Bob can cheat freely if this is
not
a Blum integer, where
p
≡
q
≡
1 (mod
n
) for primes
p
and
q
.
Exercises 5.21-5.24 contain parameters for Shamir's threshold scheme de-
scribed on pages 212-214. Use the parameters to determine the message
m
=
c
0
. Again, a computer may be necessary for some of the calculations.
5.21. Let (
t,w
)=(2
,
2),
p
= 1009, (
x
1
,m
1
)=(1
,
172), (
x
2
,m
2
)=(2
,
244).
5.22. Let (
t,w
)=(3
,
3),
p
= 3271, (
x
1
,m
1
)=(1
,
1234), (
x
2
,m
2
)=(2
,
1578),
and (
x
3
,m
3
)=(3
,
2144).
5.23. Let (
t,w
)=(4
,
4),
p
= 1433, (
x
1
,m
1
)=(3
,
372), (
x
2
,m
2
)=(5
,
859),
(
x
3
,m
3
)=(7
,
50), and (
x
4
,m
4
) = (11
,
720).
5.24. Let (
t,w
)=(4
,
4),
p
= 6367, (
x
1
,m
1
)=(7
,
3401), (
x
2
,m
2
) = (11
,
2822),
(
x
3
,m
3
) = (12
,
4239), and (
x
4
,m
4
) = (13
,
1821).
In Exercises 5.25.-5.28, use the description of Blakely's secret-sharing vector
scheme given on pages 214 and 215, to determine the message
m
for each
of the set of parameters given. Some calculations may require a computer.
5.25. Let
t
=2,
p
= 3359,
n
(1)
1
= 358;
n
(2
1
= 953; and (
c
1
,c
2
,
) = (1001
,
1111).
(
Hint: Form the equation given by
(5.4)
on page 215, and solve the equa-
tion:
A
−
1
C
(mod
p
)
.
The same hint holds for Exercises 5.26-5.28.
)
X
≡
5.26. Let
t
=3,
p
= 2551, (
c
1
,c
2
,c
3
) = (109
,
526
,
2128), and
(
n
(1
1
,n
(1
2
)=(7
,
9);
(
n
(2
1
,n
(2
2
) = (27
,
361);
(
n
(3
1
,n
(3
2
) = (100
,
2)
.
5.27. Let
t
=4,
p
= 757, (
c
1
,c
2
,c
3
,c
4
) = (26
,
399
,
711
,
192), and
(
n
(1
1
,n
(1
2
,n
(1
3
)=(3
,
21
,
31);
(
n
(2
1
,n
(2
2
,n
(2
3
)=(5
,
26
,
10);
(
n
(3
1
,n
(3
2
,n
(3
3
)=(7
,
71
,
5);
(
n
(4
1
,n
(4
2
,n
(4
3
) = (11
,
20
,
1)
.
Search WWH ::
Custom Search