Maths behind MD5

Moderator: BarsMonster

Post Reply [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
User avatar
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

Post by LordMike » Mon Dec 14, 2009 11:53 am

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

User avatar
schwarzwaldhacker
Posts: 170
Joined: Tue Apr 07, 2009 7:18 am
Location: Россия
Contact:

Re: Maths behind MD5

Post by schwarzwaldhacker » Mon Dec 14, 2009 2:59 pm

Did you look for "Schneier"?

He wrote books like:

http://www.schneier.com/book-applied.html
http://www.schneier.com/book-practical.html

And on MD5, he wrote this for instance:

http://www.schneier.com/essay-074.html

User avatar
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

Post by LordMike » Mon Dec 14, 2009 8:57 pm

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 ;)

Crucifix
[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

Post by Crucifix » Mon Dec 14, 2009 10:52 pm

I assume you've read this if you're interested in MD5, but http://www.ietf.org/rfc/rfc1321.txt

Sc00bz
Posts: 136
Joined: Fri Oct 03, 2008 8:28 am
Contact:

Re: Maths behind MD5

Post by Sc00bz » Tue Dec 15, 2009 6:39 am

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 ;)
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 co-prime 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".
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 Diffie-Hellman 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 Diffie-Hellman 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 co-prime to p. Now if p is prime then m can be any number from 1 to p-1 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.

User avatar
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

Post by LordMike » Tue Dec 15, 2009 11:02 am

Sc00bz wrote:
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 ;)
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 co-prime 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".
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 Diffie-Hellman 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 Diffie-Hellman 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 co-prime to p. Now if p is prime then m can be any number from 1 to p-1 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.
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 :P

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...

User avatar
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

Post by LordMike » Tue Dec 15, 2009 8:13 pm

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. :P

D3ad0ne
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

Post by D3ad0ne » Tue Dec 15, 2009 9:00 pm

In Diffie-Hellman 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 co-prime to p. Now if p is prime then m can be any number from 1 to p-1 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.
Off Topic but, I met Whit Diffie (from Diffie-Hellman), he was one of the better speakers I've heard.

Crucifix
[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

Post by Crucifix » Tue Dec 15, 2009 11:22 pm

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.
Hmm, and it does lehmer iterations too...

I wish they had source for that posted.

Sc00bz
Posts: 136
Joined: Fri Oct 03, 2008 8:28 am
Contact:

Re: Maths behind MD5

Post by Sc00bz » Wed Dec 16, 2009 3:48 am

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 :P
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: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)?
Yes.
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...
"different factorizations" like p * q, q * p, and 1 * p * q? Both p and q are prime.
No as they are all equivalent.

http://en.wikipedia.org/wiki/RSA_numbers
http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

User avatar
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

Post by LordMike » Wed Dec 16, 2009 10:42 pm

Interesting :)
Beginning to understand it. And oh.. About this:
Sc00bz wrote:
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...
"different factorizations" like p * q, q * p, and 1 * p * q? Both p and q are prime.
No as they are all equivalent.
Yes.. Those you talk about, are equiv.. However, what I meant was..
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 :P.

Sc00bz
Posts: 136
Joined: Fri Oct 03, 2008 8:28 am
Contact:

Re: Maths behind MD5

Post by Sc00bz » Thu Dec 17, 2009 6:51 am

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.

User avatar
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

Post by Rolf » Fri Dec 18, 2009 10:12 am

Crucifix wrote:I wish they had source for that posted.
here

Post Reply
[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
[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

Who is online

Users browsing this forum: No registered users and 1 guest