Cryptography Reference
In-Depth Information
are
p
= 107,
g
= 6, and
b
= 57. We will choose
S
= {2, 3, 5, 7}. Now, we generate some ran-
dom integers, and attempt to write powers of
g
= 6 as products of elements from
S
.
lnr of 6
24
modulo 107:
42 = 2
3
7
lnr of 6
6
modulo 107:
4 = 2
2
lnr of 6
33
modulo 107:
15 = 3
5
lnr of 6
34
modulo 107:
90 = 2
3
2
5
By taking the logarithm base 6 modulo 107 of both sides, and using the properties of dis-
crete logarithms (from proposition 43), we get the following system of congruences:
24
log2 + log3 + log7 (mod 106)
6
2
log2 (mod 106)
33
log3 + log5 (mod 106)
34
log2 + 2
log3 + log5 (mod 106)
To solve this system, we need to reduce the following matrix to row echelon form using
an analogue of Gauss-Jordan elimination for matrices representing congruences.
110124
1000 6
011033
121034
When this is done, we achieve this reduced matrix. (Verify.)
1000 3
0100104
001035
000123
Thus, we have
log
6
2 = 3
log
6
3 = 104
log
6
5 = 35
log
6
7 = 23
Now, we try to evaluate log
6,107
57 (the purpose of all this work, remember?). First, we
pick a random integer
k
= 38, and try to write
b
g
k
as a product of members of
S
. It turns
out that we can:
6
38
modulo 107 = 35 = 5
lnr of 57
7.
Search WWH ::
Custom Search