The ElGamal Algorithm provides an alternative to the RSA
for public key encryption.
1) Security of the RSA depends on the (presumed)
difficulty of factoring large integers.
2) Security of the ElGamal algorithm depends on the
(presumed) difficulty of computing discrete logs in a
large prime modulus.
ElGamal has the disadvantage that the ciphertext is twice as
long as the plaintext.
It has the advantage the same plaintext gives a different
ciphertext (with near certainty) each time it is encrypted.
Alice chooses
i) A large prime
pA (say 200 to 300 digits),
ii) A primitive element
α
A modulo
pA,
iii) A (possibly random) integer
dA with 2
≤
dA
≤
pA –2.
Alice computes
iv)
β
A
≡
α
A
dA (mod
pA).
Alice’s public key is (pA, α
A, β
A). Her private key is
dA.
Bob encrypts a short message M (M <
pA) and sends it to
Alice like this:
i) Bob chooses a random integer
k (which he keeps
secret).
ii) Bob computes
r
≡
α
A
k (mod
pA) and t ≡
βA
k
M (mod
pA), and then discards
k.
Bob sends his encrypted message (r, t) to Alice.
When Alice receives the encrypted message (
r, t), she
decrypts (using her private key
dA) by computing t r−dA.
Note tr−dA
≡
βA
k
M (
α
A
k )−dA (mod
pA)
≡ (
α
A
dA
)
k
M (
α
A
k )−dA (mod
pA)
≡ M (mod
pA)
Even if Eve intercepts the ciphertext (
r, t), she cannot
perform the calculation above because she doesn’t know
dA.
β
A
≡
α
A
dA (mod
pA), so
dA
≡ L
αA (β
A)
Eve can find
dA if she can compute a discrete log in the large
prime modulus
pA, presumably a computation that is too
difficult to be practical.
Caution: Bob should choose a different random integer
k
for each message he sends to Alice.
If M is a longer message, so it is divided into blocks, he
should choose a different
k for each block.
Say he encrypts two messages (or blocks) M1 and M2, using
the same
k, producing ciphertexts
(r1, t1) = (
α
A
k
, β
A
k
M1), (
r2, t2) = (
α
A
k
, β
A
k
M2 ).
Then t2 t1
−1 ≡ M2M1
−1 (mod
p), M2
≡ t2 t1
−1
M1 (mod
p). If
Eve intercepts both ciphertext messages and discovers one
plaintext message M1, she can compute the other plaintext
message M2.
Example: Alice chooses
pA = 107,
α
A = 2,
dA = 67, and she
computes
β
A = 267
≡ 94 (mod 107). Her public key is
( pA, α
A, β
A) = (2,67,94), and her private key is
dA = 67
Bob wants to send the message "B" (66 in ASCII) to Alice.
He chooses a random integer
k = 45 and encrypts M = 66 as
(r, t) = (
αA
k
, βA
kM)
≡ (245, 944566)
≡ (28, 9) (mod 107). He
sends the encrypted message (28, 9) to Alice.
Alice receives the message (
r, t) = (28, 9), and using her
private key
dA = 67 she decrypts to
tr−dA = 9⋅28−67
≡ 9⋅28106−67
≡ 9⋅43
≡ 66 (mod 107).
No comments:
Post a Comment