Encryption & Prime Numbers

[Alex Tweedly]

At 17:23 06/09/2004 -0700, Mark Brownell wrote:

>from here:
>http://www.guardian.co.uk/uk_news/story/0,3604,1298728,00.html
>
>I fail to see the relationship between a 32 bit word, bitXOR, and random 
>padded cypher block chaining having to do anything with Prime Numbers. As 
>far as Blowfish goes there doesn't look like there are any connections to 
>prime numbers. Perhaps AES openSSL 128 bit encryption is based on random 
>prime numbers. Any guesses as to how the above information can be 
>considered useful beyond the scope of it being a new internet urban legend?

Don't know about Blowfish specifically; it's a private-key algorithm, so 
may have no requirement on primes.

In general public/private key systems depend on the inability to decompose 
very large numbers into their prime factors. So to generate a suitable 
private key, you generate a number of primes, and multiply them together; 
if someone could easily decompose that, they would be a large part of the 
way towards discovering your private key.

More mathematically, but less understandably ...

>RSA is a public-key cryptosystem for both encryption and authentication; 
>it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. It 
>works as follows: take two large primes, p and q, and find their product n 
>= pq; n is called the modulus. Choose a number, e, less than n and 
>relatively prime to (p-1)(q-1), which means that e and (p-1)(q-1) have no 
>common factors except 1. Find another number d such that (ed - 1) is 
>divisible by (p-1)(q-1). The values e and d are called the public and 
>private exponents, respectively. The public key is the pair (n,e); the 
>private key is (n,d). The factors p and q maybe kept with the private key, 
>or destroyed.
>
>It is difficult (presumably) to obtain the private key d from the public 
>key (n,e). If one could factor n into p and q, however, then one could 
>obtain the private key d. Thus the security of RSA is related to the 
>assumption that factoring is difficult. An easy factoring method or some 
>other feasible attack would "break" RSA.
>
>Here is how RSA can be used for privacy and authentication (in practice, 
>the actual use is slightly different:
>
>RSA privacy (encryption): Suppose Alice wants to send a message m to Bob. 
>Alice creates the ciphertext c by exponentiating: c = me mod n, where e 
>and n are Bob's public key. She sends c to Bob. To decrypt, Bob also 
>exponentiates: m = cd mod n; the relationship between e and d ensures that 
>Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt.
>
>RSA authentication: Suppose Alice wants to send a message m to Bob in such 
>a way that Bob is assured that the message is authentic and is from Alice. 
>Alice creates a digital signature s by exponentiating: s = md mod n, where 
>d and n are Alice's private key. She sends m and s to Bob. To verify the 
>signature, Bob exponentiates and checks that the message m is recovered: m 
>= se mod n, where e and n are Alice's public key.
>
>Thus encryption and authentication take place without any sharing of 
>private keys : each person uses only other people's public keys and his or 
>her own private key. Anyone can send an encrypted message or verify a 
>signed message, using only public keys, but only someone in possession of 
>the correct private key can decrypt or sign a message.

(quote from www.anujseth.com)
-- Alex.