# Encryption & Prime Numbers

Alex Tweedly alex at tweedly.net
Mon Sep 6 21:06:20 EDT 2004

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