compare RSA and D-Hellman

0 views
Skip to first unread message

sa...@apiary.sumy.ua

unread,
Mar 24, 1999, 3:00:00 AM3/24/99
to
hi

sorry, if this is duplicate message - i've got an error with news-server.


i wonder, if there was ever found any weakness in Diffie-Hellman's algorithm
(yes, that old-old algorithm :).

i know it as SKIP algorithm, but i am not sure if it is a common name for
it. ( you know, shared_secret = a^(p*q) mod n )

i suppose, there was found some weakness, or why should they have to develop
RSA? for this so called "skip" algorithm is much-much more easy to
implement. and it seems to me to be not the less strong.


i did not use any software, endrypting with RSA, so i'd like to know, how
fast it enciphers.

thanks for any reply.
--
Sassa

Apiary Inc.
______
@()(_)
/\\

sa...@apiary.sumy.ua

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own

tomst...@my-dejanews.com

unread,
Mar 24, 1999, 3:00:00 AM3/24/99
to
<snip>

DH is the a^(x*y). However DH is not an encryption algorithm. The goal of DH
is to share a secret number (key).

RSA is C = P^e mod PQ, and has the inverse exponent P = C^d mod PQ, where 'd'
and 'e' are discrete-inverses.

The only weakness in public key systems are imposters. For example in DH,
person A wants to talk to person B, but must go thru person C. Person C could
pretend to be the other person.. i.e

ideal:
A --> C --> B
A <-- C <-- B

man-in middle attack: When A tries to send to B, C pretends he is B. But
still relays the info to B. When C sends to B he pretends he is A. etc...

You can do the same with RSA.

A ---> C ---> B (with RSA key of A)
With rsa key of B A <--- C <--- B

Attack:

A --> C ----> B (key of C)
With key of C A <--- C <---- B


Etc...

Tom

Doug Stell

unread,
Mar 24, 1999, 3:00:00 AM3/24/99
to

>i wonder, if there was ever found any weakness in Diffie-Hellman's algorithm
>(yes, that old-old algorithm :).

It is still believed that the conjecture that D-H is a difficult to
break as it is to do a discrete log is true. Therefore, the algorithm
has no known weaknesses, but it is possible to pick a weak prime
modulus.

>i know it as SKIP algorithm, but i am not sure if it is a common name for
>it. ( you know, shared_secret = a^(p*q) mod n )

SKIP is one of many protocols that use the D-H key agreement protocol.
SKIP's use, however, is extremely limited.

>>i suppose, there was found some weakness, or why should they have to develop
>>RSA?

There are hundreds of public key algorithms, if you count all the
varients. So, you could ask the same about any of them.

D-H is a key agreement algorithm and the basis of a lot of other
algorithms. It did not provide a reversible encryption or signature
capability. That's what prompted the development of RSA and ElGamal.

RSA and D-H simply serve very different purposes.

>>i did not use any software, endrypting with RSA, so i'd like to know, how
>>fast it enciphers.

In general, the time required is roughlyt proportional to the number
of bits in the exponent plus the number of those bits that are 1's.
Since most implementations use a small public exponent, the public
operation is very fast, while the private operation is slow.

D-H uses the same math function, modular exponentiation. However, the
first half of the calculation is often done with a small base, which
makes that calculation a little faster.

>The only weakness in public key systems are imposters. For example in DH,
>person A wants to talk to person B, but must go thru person C. Person C could
>pretend to be the other person.. i.e
>
>ideal:
>A --> C --> B
>A <-- C <-- B
>
>man-in middle attack: When A tries to send to B, C pretends he is B. But
>still relays the info to B. When C sends to B he pretends he is A. etc...
>
>You can do the same with RSA.

This is addressed by the use of certificates or any other means by
which you know for sure who's public key you are using. You simply
need to use an authenticated public key.

BTW, this is not the only known weakness systems can have. You can do
lots of things wrong or fail to so some things right and have a
weakness. If you do the right things and avoid the wrong things,
public key schemes are very secure.


DJohn37050

unread,
Mar 24, 1999, 3:00:00 AM3/24/99
to
BTW, Dan Boneh has recently proved that attacking ECDH is fully exponential if
ECDLP is. This analogous statements are not (known to be) true for DH and DLP
and RSA and IFP.
Don Johnson

Sassa

unread,
Mar 24, 1999, 3:00:00 AM3/24/99
to
hi

> It is still believed that the conjecture that D-H is a difficult to
> break as it is to do a discrete log is true. Therefore, the algorithm
> has no known weaknesses, but it is possible to pick a weak prime
> modulus.

_prime_ modulus? i thought, i could pick _any_ modulus, even not so
prime ;)

or should i pick prime modulus for more security? or is it easy to break
D-H if modulus is not prime?


> SKIP is one of many protocols that use the D-H key agreement protocol.

aha, i see.


> There are hundreds of public key algorithms, if you count all the
> varients. So, you could ask the same about any of them.

yes, i could ask question about any of them.

i thought, one should devise a new encryption standard if existing
algorithms do not fit his requirements.


> D-H is a key agreement algorithm and the basis of a lot of other
> algorithms. It did not provide a reversible encryption or signature
> capability.

why cannot someone generate, say, 56 bit D-H key, and use the shared secret
for DES ? so this way one can exchange keys in public, still secure enough.
and then use those keys for DES. or any other algorithm that demands
symmetrical keys.


> That's [D-H] what prompted the development of RSA and ElGamal.

and so i thought too: D-H prompted RSA.


> RSA and D-H simply serve very different purposes.

not so different, as to my sight of view. main purpose to create algorithm
for sharing keys publicly. although RSA also includes encryption
(and, what is even more essential, decryption :) algorithm.


>>>...RSA, so i'd like to know, how
>>>fast it enciphers.

> In general, the time required is roughlyt proportional to the number
> of bits in the exponent plus the number of those bits that are 1's.
> Since most implementations use a small public exponent, the public
> operation is very fast, while the private operation is slow.

ok, how long does it take, say, P-100 to encipher, say, 100K? in average.


> D-H uses the same math function, modular exponentiation. However, the
> first half of the calculation is often done with a small base, which
> makes that calculation a little faster.

i generate 128 _Byte_ D-H keys within ~20 seconds on AMD 5x (about 100MHz).

are these keys secure, if i take modulus n=2^(128*8) - as you see, not prime
at all?

i do not use any prime. does my implementation has a way to be broken?

Sassa

unread,
Mar 24, 1999, 3:00:00 AM3/24/99
to
hi

i am new to here, so would you please expand these for me:
ECDH, ECDLP, DLP, IFP?
what do they stand for?

DJohn37050

unread,
Mar 24, 1999, 3:00:00 AM3/24/99
to
ECDH = Elliptic Curve Diffie Hellman
ECDLP = Elliptic Curve Discrete Logarithm Problem
IFP = Integer Factorization Problem
DLP = (Normal) Discrete Logarithm Problem, over a finite field.
Don Johnson

tomst...@my-dejanews.com

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
Here is the actual (I believe :) ) method for picking DH values.


Pick a large prime A, share that between the two people.

Person1 picks another large prime ( call it x ), that is relatively prime to A
(note: if his private number x is prime then you need not check this).

Person2 picks another large prime (call it y).

Person one sends A^x and person two sends A^y. They both can now calculate
A^(x*y).


If A is not prime you run into the chance of x mod A = 0.

Scott Fluhrer

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
In article <7dbvh5$5a9$1...@nnrp1.dejanews.com>,
tomst...@my-dejanews.com wrote:

>Here is the actual (I believe :) ) method for picking DH values.
>
>
>Pick a large prime A, share that between the two people.

They also pick a number g (and, it helps security if that number is a "generator"
for prime A, that is, g^x mod A takes on A-1 possible values. That are always
lots of generators for any prime A, and if you can factor A-1, it's easy to test
a candidate g to see if it's a generator (and, you can pick an A where you know
the factorization of A-1, so the difficulty of factorization is not a problem
here)


>
>Person1 picks another large prime ( call it x ), that is relatively prime to A
>(note: if his private number x is prime then you need not check this).

Actually, x need not be prime, and having 0 <= x < A-1 is sufficient (and,
strictly speaking, not necessary -- a larger range just doesn't give you any
additional security)


>
>Person2 picks another large prime (call it y).

Again, y does not need to be prime


>
>Person one sends A^x and person two sends A^y. They both can now calculate
>A^(x*y).

Nope: person one sends g^x mod A and person two sends g^y mod A. They both can
now calculate g^(x*y) mod A.

After all, A^x and A^y are bound to be *extremely* large numbers. For example,
if A and x for both 512 bits, A^x is circa 10^160 digits long, and you probably
won't be able to send a number that large over a network connection before the
heat death of the universe.


>
>
>If A is not prime you run into the chance of x mod A = 0.

So? That doesn't mean g^x mod A (or A^x for that matter) is any particular
value.

A real reason for making A prime is to make the DLP harder: for composite A,
all the attacker does is take the factorization of A, and solve the DLP for
each component prime. This is a lot easier than solving the DLP for a
similarly sized prime A.

--
poncho


Sam Simpson

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
Don,

Have you got a pointer to further information on this?


Regards,

--
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because
he's kill filed. See http://www.openpgp.net/FUD for why!


DJohn37050 wrote in message
<19990324140655...@ng16.aol.com>...

tomst...@my-dejanews.com

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
so let me see if I understand:

A -> large prime number
x,y -> large private numbers (not prime)
g -> small random number?

Is that right? Can 'a' be static?

DJohn37050

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
ANSI X9.42 or IEEE P1363 discuss DH and also security considerations for same.
X9.42 is a draft available by attending an ANSI X9F1 meeting. IEEE P1363 is
available on the web. Just search on "IEEE P1363". There are many
considerations. The field order p should be generated by a canonically random
process to thwart an attack by Dan Gordon, for example.
Don Johnson

bo...@rsa.com

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
In article <7dc30r$6...@dfw-ixnews3.ix.netcom.com>,

Scott Fluhrer <sflu...@ix.netcom.com> wrote:
> In article <7dbvh5$5a9$1...@nnrp1.dejanews.com>,
> tomst...@my-dejanews.com wrote:

stuff deleted, most of which was correct, except:


>
> A real reason for making A prime is to make the DLP harder: for composite A,
> all the attacker does is take the factorization of A

And if A is 1024 bits, (say) please explain how one achieves this
factorization?

The real reason for taking A prime is that we want the exponentiation to
take place in a cyclic group. i.e. it can be generated by just one element.


>, and solve the DLP for
> each component prime. This is a lot easier than solving the DLP for a
> similarly sized prime A.

Yes. If the factorization can be obtained. That is a big if.

Sassa

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
hi

> Pick a large prime A, share that between the two people.

i suppose, A is not a secret? so if someone else knows it nothing harmful
happens? during following quadrillion years? ;)

> Person1 picks another large prime ( call it x ), that is relatively prime to A
> (note: if his private number x is prime then you need not check this).

> Person2 picks another large prime (call it y).

> Person one sends A^x and person two sends A^y. They both can now calculate
> A^(x*y).

i knew, algorithm is like this. but i was inclined to think that A, x, y and
N were random numbers with no restrictions?

i thought, i do not need to calculate any primes or to check for relative
primes, thus _much_ more easy to implement.

or if i choose some specific combination of non-prime A, x, y and N there's
some non-zero possibility to break it in a couple of days?


> If A is not prime you run into the chance of x mod A = 0.

what if x mod A == 0? sorry, i am not familiar with what modulus
algebra says upon this occasion :(

anyway, i can make x odd and less than A: just set the msb in A to 1, and
set msb in x to 0. to make x odd - just set lsb to 1 (odd, so it will always
be non-zero). thus x mod A will always be x!=0. anyway, i am using flat
pascal randomize routine, so it cannot generate 128 zero bytes at one time
;) (i was using that weak randomize routine for i was just going to make
sure DH works :))))).


btw, thanks to DJohn for expanding ECDH, etc for me...

Harv

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
A and g can be static and public; in fact, If A and g are static and public,
then you can evolve DH into the ElGamal public key system.

For the best setup, g shouldn't really be a small random number. g should be
a generator of A. g is a generator if and only if the only X that satisfies
g^X = 1 mod A is X=A-1. For example 3 is a generator of 7, but 2 is not.

However, if A is a randomly picked prime, then it can be difficult to tell
if g is a generator. You need to know the factorization of A-1. If you know
the factors of A-1 then g is a generator if g^x=1 mod A and g^b!=1 mod A for
any b that divides A-1.

So, you best bet is to pick a large prime p, and test if 2*p+1 is also
prime. If this is the case then set A=2*p+1, and start the hunt for a
generator.

Harv
Red...@SomeYahoo.com
Remove the Some to send email.

<tomst...@my-dejanews.com> wrote in message
news:7dd7q3$6ln$1...@nnrp1.dejanews.com...


> so let me see if I understand:
>
> A -> large prime number
> x,y -> large private numbers (not prime)
> g -> small random number?
>
> Is that right? Can 'a' be static?
>
> Tom
>

DJohn37050

unread,
Mar 25, 1999, 3:00:00 AM3/25/99
to
See IEEE P1363. It is best if g does not generate A but generates a prime
order subgroup. Pohlig Hellman says that this is what dominates the strength
formula anyway.
Don Johnson

Scott Fluhrer

unread,
Mar 26, 1999, 3:00:00 AM3/26/99
to
In article <7ddla3$ig6$1...@nnrp1.dejanews.com>,
bo...@rsa.com wrote:

>In article <7dc30r$6...@dfw-ixnews3.ix.netcom.com>,
> Scott Fluhrer <sflu...@ix.netcom.com> wrote:
>> In article <7dbvh5$5a9$1...@nnrp1.dejanews.com>,
>> tomst...@my-dejanews.com wrote:
>
>stuff deleted, most of which was correct, except:
>
>
>>
>> A real reason for making A prime is to make the DLP harder: for composite A,
>> all the attacker does is take the factorization of A
>
>And if A is 1024 bits, (say) please explain how one achieves this
>factorization?

Well, [gulp] yes, that is a problem. I was sort of assuming that the
factorization was publicly known.

>
>The real reason for taking A prime is that we want the exponentiation to
>take place in a cyclic group. i.e. it can be generated by just one element.

Yup, you're right. Although, I thought [pathetically weak defense warning]
that many composites had quasi-generators, which had elements of order
phi(N) (although I also know that some composites do not). Looks like it's
time for me to hit the books again...


>
>
>>, and solve the DLP for
>> each component prime. This is a lot easier than solving the DLP for a
>> similarly sized prime A.
>
>Yes. If the factorization can be obtained. That is a big if.

^^^
Hey! I was at least slightly right!

--
poncho

Scott Fluhrer

unread,
Mar 26, 1999, 3:00:00 AM3/26/99
to
In article <7denj3$9...@sjx-ixn10.ix.netcom.com>,
Scott Fluhrer <sflu...@ix.netcom.com> wrote:

> Although, I thought [pathetically weak defense warning]
>that many composites had quasi-generators, which had elements of order
>phi(N) (although I also know that some composites do not). Looks like it's
>time for me to hit the books again...

Man, I really should learn to hit the books first, and then post. The only
composites that have such "quasi-generators" are composites of the forms
4, p^i and 2*p^j, where p is an odd prime, i>=2 and j>=1

Ok, can I slink away now?

--
poncho


Sassa

unread,
Mar 26, 1999, 3:00:00 AM3/26/99
to
> See IEEE P1363.

thank you.

where can i find it on the net?

Sassa

unread,
Mar 26, 1999, 3:00:00 AM3/26/99
to
hey, it seems you've rambled a bit,

so, i'll type my question again:

0. define A = 2^(128*8) = '1' and 128 zero bytes.
1. choose random 128 byte g and distribute it to the second party.
2. first party generates random x.
3. second party generates random y.
4. parties exchange g^x mod A and g^y mod A respectively.
5. now they can exchange messages, encrypted with
shared_secret key= g^(x*y) mod A

will it be easy for the third party knowing g, A, g^x mod A and g^y mod A
to calculate x and y? or maybe there exists z that g^(x*y) mod A= g^(x*z)
mod A if A is not prime or it does not accord to any other restriction?

as you see, factorization of A is obvious...
(if i understand 'factorization' term ok :)


i hope that....

bo...@rsa.com

unread,
Mar 26, 1999, 3:00:00 AM3/26/99
to
In article <ADCYq...@apiary.sumy.ua>,

sa...@apiary.sumy.ua wrote:
> hey, it seems you've rambled a bit,
>
> so, i'll type my question again:

May I suggest to everyone that they READ about this subject before discussing
it further? The RSA FAQ has a good discussion, as does the HAC or Schneier's
book.

Medical Electronics Lab

unread,
Mar 26, 1999, 3:00:00 AM3/26/99
to
Sassa wrote:
>
> > See IEEE P1363.
>
> thank you.
>
> where can i find it on the net?

http://grouper.ieee.org/groups/1363/draft.html

Patience, persistence, truth,
Dr. mike

Reply all
Reply to author
Forward
0 new messages