Practical improvement of DH-ElGamal scheme
- From: "mega_bit8" <mega_bit8@xxxxxxxxx>
- Date: Sun, 7 May 2006 22:41:09 -0700 (PDT)
Hello, my name is Badita Robert, I'm 24 and I live in Romania.
Improving DH-ElGamal public key encryption scheme can be done in
removing the need for the random number generator involved in process
and also the complete alleviation of the message doubling.
My ideea of improving DH-ElGamal over for example Galois Fields
GF(2^bits) starts as following:
1. GLOBAL PUBLIC DATA:
a. Define an irreducible polynome P with g1 and g2 both
generators mod P.
b. Define scramble1(x)= g1^x mod P and scramble2(x)= g2^x
mod P
2. Public/Secret key generation (same as Diffie-Hellman key
agreement)
For person Alice:
a. Choose secret parameter a= random(2^bits)
b. Compute public parameter Pa= g1^a mod P= scramble1(a)
c. Linking between 2 persons (Alice and Bob):
c1. Compute Pb^a mod P= Pa^b mod P= g1^(a*b) mod
P= secret session key and noted by SSK (computed safely by both Alice
and Bob)
3. Pre-Encryption step (computed by both persons):
a. Let Q= scramble1(SSK) and increment Q until Q=
irreducible
b. Let e= scramble2(SSK) and increment e until e mod
every divisor of (2^bits -1) >= 2; this assures gcd(e, 2^bits -1)= 1
and strenghtens message encryption mod Q. Fermat numbers up to F(11)
have known factorization, this means that this method can be used up to
"bits= 4096".
c. Let d= e^-1 mod (2^bits -1); inverse exists
4. Encryption: Alice send to Bob:
C= M^e mod Q; M= message, C= encrypted message, e=
encode exponent, Q= new secret modulus (known only by Alice and Bob).
5. Decryption: Bob computes:
M= C^d mod Q; which is correct since e*d= 1 mod (2^bits
-1)
The most time consuming step of the algorithm is step 3.a. ->
making Q irreducible, but Q is computed only once per session and can
be cached near the secret key.
Step 3.b. runs fast but requires the complete factorization of
Fermat numbers since for example 2^4096 -1= 3*5*17*257*...*F(10)*F(11),
note that F(5..11) are composite. We consider F_DIV[0..N] as all prime
divisors of 2^bits -1. The fact that e mod F_DIV[K]>= 2 assures that
every message M that is a F_DIV[K] root of 1 mod Q is encoded to C with
C <> M, this also works for roots that are products of F_DIV-s, and
makes generally C <> M.
Scramble1 and 2 are defined as modular exponentiation for
better security although other simple scramblers may be used since they
operate on SSK known only by Alice and Bob, by DLP and DHP.
Attacking this encryption scheme:
Eve knows: P, g1, g2, scramble1, scramble2, Pa, Pb, C and
possibly M
Eve doesn't know (tries to compute): SSK, Q, e, d
Eve doesn't know SSK by DLP and DHP and so it is hard for her
to compute Q or e since it requires another DLP computation mod P. For
Eve to compute d, she must know e.
The start of attacking this scheme is knowing a relation like
C= M^2 mod Q and Eve tries to recover Q knowing C and M, although this
kind of relations are very unlikely to appear in practice. So one
approach I see is to find relations like C= M^t mod Q for small t, but
Eve doesn't know Q in first place so she cannot develop a text based
attack to find relation like this one.
Note that sending C doesn't require additional RNG or
additional send parameters.
Badita Robert, Romania
.
- Next by Date: Single cycle functions
- Next by thread: Single cycle functions
- Index(es):
Relevant Pages
|
