![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
Example 5.5 Suppose p = 19, α = 2 and β = 6. Since the example is so small, we can tabulate the values of L1 (γ) and L2 (γ) for all Hence, log2 6 = 11102 = 14, as can easily be verified. It is possible to give formal proof of the algorithms correctness using mathematical induction. Denote For i ≥ 0, define Also, define β0 to be the value of β in step 2 of the algorithm; and, for i ≥ 1, define βi to be the value of β in step 11 during the ith iteration of the while loop. It can be proved by induction that
for all i ≥ 0. Now, with the observation that it follows that i ≥ 0. Since the algorithm is correct. The details are left to the reader. 5.2 Finite Field and Elliptic Curve SystemsWe have spent a considerable amount of time looking at the Discrete Logarithm problem and the factoring. We will see these two problems again and again, underlying various types of cryptosystems and cryptographic protocols. So far, we have considered the Discrete Logarithm problem in the finite field The ElGamal Cryptosystem can be implemented in any group where the Discrete Log problem is intractible. We used the multiplicative group It is easy to define an ElGamal Cryptosystem in the subgroup H in a similar fashion as it was originally described in
Lets now turn to the generalized Discrete Log problem. The subgroup H generated by any α ∈ G is of course a cyclic group of order |H|. So any version of the problem is equivalent, in some sense, to the Discrete Log problem in a cyclic group. However, the difficulty of the Discrete Log problem seems to depend in an essential way on the representation of the group that is used. As an example to illustrate a representation where the problem is easy to solve, consider the additive cyclic group Since gcd(α, n) = 1, α has a multiplicative inverse modulo n, and we can compute α-1 mod n easily using the Euclidean algorithm. Then we can solve for a, obtaining
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |