Maths behind MD5
Moderator: BarsMonster
 LordMike
 Posts: 184
 Joined: Tue Feb 10, 2009 8:34 am [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Maths behind MD5
Hey,
Does someone have a good / great article on the maths behind MD5?
Really, anything will do.. I need an introduction to the Mathematics behind cryptographic algorithms..
I'm a little into the use of large prime numbers already.. Got a book on the subject which I'm reading..
Regards,
 Mike
Does someone have a good / great article on the maths behind MD5?
Really, anything will do.. I need an introduction to the Mathematics behind cryptographic algorithms..
I'm a little into the use of large prime numbers already.. Got a book on the subject which I'm reading..
Regards,
 Mike
 schwarzwaldhacker
 Posts: 170
 Joined: Tue Apr 07, 2009 7:18 am
 Location: Россия
 Contact:
Re: Maths behind MD5
Did you look for "Schneier"?
He wrote books like:
http://www.schneier.com/bookapplied.html
http://www.schneier.com/bookpractical.html
And on MD5, he wrote this for instance:
http://www.schneier.com/essay074.html
He wrote books like:
http://www.schneier.com/bookapplied.html
http://www.schneier.com/bookpractical.html
And on MD5, he wrote this for instance:
http://www.schneier.com/essay074.html
 LordMike
 Posts: 184
 Joined: Tue Feb 10, 2009 8:34 am [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Re: Maths behind MD5
Interesting.. But not so close to what I'm looking for...
Right now, I'm looking for an explanation as to why prime numbers are so damn interesting in assymetric cryptography.. Other than that they're only divisable by 1 and themselves....
Else, thanks for the link
Right now, I'm looking for an explanation as to why prime numbers are so damn interesting in assymetric cryptography.. Other than that they're only divisable by 1 and themselves....
Else, thanks for the link
Re: Maths behind MD5
I assume you've read this if you're interested in MD5, but http://www.ietf.org/rfc/rfc1321.txt
Re: Maths behind MD5
With RSA two large primes, p and q, are multiplied together and is given as the public key, m. There is also an exponent, e, which is coprime to (q  1) * (p  1), normally it is 65537. The private exponent is found by solving for E in E*e = 1 (mod ((q  1) * (p  1))) "(E * e) % ((q  1) * (p  1)) == 1".LordMike wrote:Interesting.. But not so close to what I'm looking for...
Right now, I'm looking for an explanation as to why prime numbers are so damn interesting in assymetric cryptography.. Other than that they're only divisable by 1 and themselves....
Else, thanks for the link
For encrypting a message t: c = t ^ e (mod m)
For decrypting cipher text c: d = c ^ E (mod m)
d should be the same as t you original message.
RSA and other asymmetric encryption algorithms are usually used to share a random key used in a symmetric encryption algorithm like AES or RC4 (why is RC4 more common than AES in SSL certs even though RC4 is broken?).

With DiffieHellman b (base) and p (prime) are public. Then user a picks a random number A and user b picks a random number B. They exchange b ^ A (mod p) and b ^ B (mod p). Then user a calculates (b ^ B) ^ A (mod p) and user b calculates (b ^ A) ^ B (mod p) which are both equal. They use that number as a key in a symmetric encryption algorithm like AES or RC4. Ohh boo I totally forgot about b (base) needs to be a primitive root mod p (prime). Apparently in practice b is usually either 2 or 5.
Ehh just look at Wikipedia they're very thorough:
http://en.wikipedia.org/wiki/RSA
http://en.wikipedia.org/wiki/Diffie%E2% ... y_exchange

I just noticed that I didn't answer your question. In DiffieHellman if p is not prime bad things happen because b needs to be a primitive root mod p. Which mean that for any n: m = b ^ n (mod p), m is coprime to p. Now if p is prime then m can be any number from 1 to p1 but if p is not prime then there are "holes" in that range that m can not be. Making you do more work to get the same number of possible keys.
 LordMike
 Posts: 184
 Joined: Tue Feb 10, 2009 8:34 am [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Re: Maths behind MD5
Interesting...Sc00bz wrote:With RSA two large primes, p and q, are multiplied together and is given as the public key, m. There is also an exponent, e, which is coprime to (q  1) * (p  1), normally it is 65537. The private exponent is found by solving for E in E*e = 1 (mod ((q  1) * (p  1))) "(E * e) % ((q  1) * (p  1)) == 1".LordMike wrote:Interesting.. But not so close to what I'm looking for...
Right now, I'm looking for an explanation as to why prime numbers are so damn interesting in assymetric cryptography.. Other than that they're only divisable by 1 and themselves....
Else, thanks for the link
For encrypting a message t: c = t ^ e (mod m)
For decrypting cipher text c: d = c ^ E (mod m)
d should be the same as t you original message.
RSA and other asymmetric encryption algorithms are usually used to share a random key used in a symmetric encryption algorithm like AES or RC4 (why is RC4 more common than AES in SSL certs even though RC4 is broken?).

With DiffieHellman b (base) and p (prime) are public. Then user a picks a random number A and user b picks a random number B. They exchange b ^ A (mod p) and b ^ B (mod p). Then user a calculates (b ^ B) ^ A (mod p) and user b calculates (b ^ A) ^ B (mod p) which are both equal. They use that number as a key in a symmetric encryption algorithm like AES or RC4. Ohh boo I totally forgot about b (base) needs to be a primitive root mod p (prime). Apparently in practice b is usually either 2 or 5.
Ehh just look at Wikipedia they're very thorough:
http://en.wikipedia.org/wiki/RSA
http://en.wikipedia.org/wiki/Diffie%E2% ... y_exchange

I just noticed that I didn't answer your question. In DiffieHellman if p is not prime bad things happen because b needs to be a primitive root mod p. Which mean that for any n: m = b ^ n (mod p), m is coprime to p. Now if p is prime then m can be any number from 1 to p1 but if p is not prime then there are "holes" in that range that m can not be. Making you do more work to get the same number of possible keys.
As for encrypting message "t".. Is t the entire text, made into one large number?..
Or is it for every character in t?..
That's one of the things I've never quite understood about this
Anyhow
So the entire security, for RSA, is based on the fact that the public key, pq, is *very* large.. And as such it is hard to find the "private key" (p and q respectively)?
Also.. Given a public key.. I assume it's possible to find different factorizations .. Is it necessary to check each of the factorizations possible, as only one of them is 'correct' ? .. Ofc. making it even harder... / longer...
 LordMike
 Posts: 184
 Joined: Tue Feb 10, 2009 8:34 am [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Re: Maths behind MD5
Understanding more about RSA... And why factorizing is interesting...
I found this Java application: http://www.alpertron.com.ar/ECM.HTM. It uses Elliptic curves to factorize numbers. And has no limit (System limited) to the size of the input.
For a test, I entered my own digital certificates public key into it.
I found this Java application: http://www.alpertron.com.ar/ECM.HTM. It uses Elliptic curves to factorize numbers. And has no limit (System limited) to the size of the input.
For a test, I entered my own digital certificates public key into it.

 Posts: 111
 Joined: Fri Sep 04, 2009 5:37 pm [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Re: Maths behind MD5
Off Topic but, I met Whit Diffie (from DiffieHellman), he was one of the better speakers I've heard.In DiffieHellman if p is not prime bad things happen because b needs to be a primitive root mod p. Which mean that for any n: m = b ^ n (mod p), m is coprime to p. Now if p is prime then m can be any number from 1 to p1 but if p is not prime then there are "holes" in that range that m can not be. Making you do more work to get the same number of possible keys.
Re: Maths behind MD5
Hmm, and it does lehmer iterations too...LordMike wrote:Understanding more about RSA... And why factorizing is interesting...
I found this Java application: http://www.alpertron.com.ar/ECM.HTM. It uses Elliptic curves to factorize numbers. And has no limit (System limited) to the size of the input.
I wish they had source for that posted.
Re: Maths behind MD5
It is normally just a large random number (like 128 bits) used as an encryption key for a symmetric encryption algorithm. RSA can only encrypt numbers greater than 1 and less than p*q (I think... hmm Wikipedia says greater than 0, but if you encrypt 1 you'll get 1 as your cipher text).LordMike wrote:Interesting...
As for encrypting message "t".. Is t the entire text, made into one large number?..
Or is it for every character in t?..
That's one of the things I've never quite understood about this
Yes.LordMike wrote:Anyhow
So the entire security, for RSA, is based on the fact that the public key, pq, is *very* large.. And as such it is hard to find the "private key" (p and q respectively)?
"different factorizations" like p * q, q * p, and 1 * p * q? Both p and q are prime.LordMike wrote:Also.. Given a public key.. I assume it's possible to find different factorizations .. Is it necessary to check each of the factorizations possible, as only one of them is 'correct' ? .. Ofc. making it even harder... / longer...
No as they are all equivalent.
http://en.wikipedia.org/wiki/RSA_numbers
http://en.wikipedia.org/wiki/RSA_Factoring_Challenge
 LordMike
 Posts: 184
 Joined: Tue Feb 10, 2009 8:34 am [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Re: Maths behind MD5
Interesting
Beginning to understand it. And oh.. About this:
What if we find several different p's and q's?.. Like, for pq=20:
p=4 and q=5 or p=2 and q=10... Those are not equivalent?...
I'm assuming I'll just have to decrypt my message with the different sets of pq I find along the way, and see which one makes most sence .
Beginning to understand it. And oh.. About this:
Yes.. Those you talk about, are equiv.. However, what I meant was..Sc00bz wrote:"different factorizations" like p * q, q * p, and 1 * p * q? Both p and q are prime.LordMike wrote:Also.. Given a public key.. I assume it's possible to find different factorizations .. Is it necessary to check each of the factorizations possible, as only one of them is 'correct' ? .. Ofc. making it even harder... / longer...
No as they are all equivalent.
What if we find several different p's and q's?.. Like, for pq=20:
p=4 and q=5 or p=2 and q=10... Those are not equivalent?...
I'm assuming I'll just have to decrypt my message with the different sets of pq I find along the way, and see which one makes most sence .
Re: Maths behind MD5
4 is not prime and 20 is not a valid modulus as it has more than 3 numbers (including 1) that divide it.
The only numbers that divide p are p and 1.
The only numbers that divide q are q and 1.
When you multiply p and q, it will only be divisible by p, q, and 1.
The only numbers that divide p are p and 1.
The only numbers that divide q are q and 1.
When you multiply p and q, it will only be divisible by p, q, and 1.
 Rolf
 Posts: 122
 Joined: Fri Dec 26, 2008 10:48 am [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Re: Maths behind MD5
hereCrucifix wrote:I wish they had source for that posted.
Who is online
Users browsing this forum: No registered users and 1 guest