trying to understand Diffie Hellman/RSA and Ellipical Curve Algorithms

Posted on 2009-07-13
Medium Priority
Last Modified: 2012-05-07
I have been studying for the CISSP, and how these algorithms function really intrigue me.  Unfortunately, I took stats, finite math, and trig.  I didn't take calc.

Can someone recommend a good book for those behind in math can understand these?  Elliptical Curve is the only one that somewhat makes sense.  

Your thought and insights would be helpful.

Question by:NYGiantsFan
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
LVL 33

Expert Comment

by:Dave Howe
ID: 24849045
what is it you are trying to understand? the usage, or the formal proofs?

Author Comment

ID: 24849357
well. something that will break this down for curious dummies.
 modulus ?


Key generation
RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys for the RSA algorithm are generated the following way:

1.Choose two distinct prime numbers p and q.
For security purposes, the integers p and q should be chosen uniformly at random and should be of similar bit-length. Prime integers can be efficiently found using a Primality test.
2.Compute n = pq.
n is used as the modulus for both the public and private keys
3.Compute the totient: .
4.Choose an integer e such that , and e and  share no divisors other than 1 (i.e. e and  are coprime).
e is released as the public key exponent.
Choosing e having a short addition chain results in more efficient encryption. Small public exponents (such as e=3) could potentially lead to greater security risks.[2]
5.Determine d (using modular arithmetic) which satisfies the congruence relation .
Stated differently, ed  1 can be evenly divided by the totient (p  1)(q  1).
This is often computed using the Extended Euclidean Algorithm.
d is kept as the private key exponent.
The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d which must be kept secret.

Notes on some variants:

PKCS#1 v2.0 and PKCS#1 v2.1 specifies using , where lcm is the least common multiple instead of .
For efficiency the following values may be precomputed and stored as part of the private key:
p and q: the primes from the key generation,
 and ,

[edit] Encryption
Alice transmits her public key (n,e) to Bob and keeps the private key secret. Bob then wishes to send message M to Alice.

He first turns M into an integer 0 < m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to:

This can be done quickly using the method of exponentiation by squaring. Bob then transmits c to Alice.
LVL 33

Expert Comment

by:Dave Howe
ID: 24849776
ok. the totient is (p-1)(q-1) provided p and q are prime.

the reason for this is that the totient of a number is the number of integers that are relatively prime to it - and if p is prime, then there are p-1 other numbers relatively prime to it (and similarly for q)

the modulus function is the old "remainder" function you may remember from kindergarden division - where 8/5 isn't 1.6 but "one remainder 3"

it finds a place in integer math, where integer division only ever gives an integer as result, discarding the fractional part of the answer. from the above example:

modular math is also occasionally called "clock math" as the most common example is a clock - where minutes are modulo 60 and hours modulo 12 or 24 depending on where you were brought up :)

so, 27 hours is always 1 day 3 hours, not 1.125 days :)
LVL 33

Accepted Solution

Dave Howe earned 2000 total points
ID: 24849880
so, from the above RSA:

find two prime numbers p and q

calculate n (where n is pq)

calculate x (where x is (p-1)(q-1)

choose some arbitrary integer e (where e < x/2) (512 is a common choice)

calculate d such that d times e modulo x is equal to 1 (the integer division result may be larger than 1 if this is easier)

for fairly complex reasons, for any integer m, the value of "m to the power (de) modulo n" is equal to m

therefore, "(m to the power of e mod n) to the power of d mod n", because it is the same as "m to the power (de) mod n", is equal to m

so by calculating some cyphertext value c equal to "m to the power of e mod n" then calculating "c to the power of d mod n" you get back the original m.

the bit that gets handwaved over there is the the proof for "(m^de)%n=m" :)


Author Comment

ID: 24860373
Thanks.  I am going to print this out and try to understand when I have some time.  Thanks again Dave!

Featured Post

Learn how to optimize MySQL for your business need

With the increasing importance of apps & networks in both business & personal interconnections, perfor. has become one of the key metrics of successful communication. This ebook is a hands-on business-case-driven guide to understanding MySQL query parameter tuning & database perf

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

The recent Petya-like ransomware attack served a big blow to hundreds of banks, corporations and government offices The Acronis blog takes a closer look at this damaging worm to see what’s behind it – and offers up tips on how you can safeguard your…
The well known Cerber ransomware continues to spread this summer through spear phishing email campaigns targeting enterprises. Learn how it easily bypasses traditional defenses - and what you can do to protect your data.
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…
Suggested Courses
Course of the Month8 days, 8 hours left to enroll

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question