Can someone briefly explain or direct me to somewhere where I can find out about the basic idea behind encryption methods and what the relation to prime numbers is?

Thanks

Prime numbers play a major role in an encryption proccess called RSA. In-order for me to continue, I must know what you know about congruences, euler's phi function (and its relation to congruences).

Yatir

Is that correct?

By Yatir Halevi on Sunday, December 01, 2002 - 04:26 pm:

Yes, you are correct.
All you need to know is that

$a^{\varphi (n)}=1$ (mod $n$)

Fermat's little theorem is a special case of this relation (discovered by Euler), since $\varphi (p)=p-1$ for prime $p$.
The idea behind RSA (Invented by R. Rivest, A. Shamir and L. Adleman) encryption is the following:
Let's say you want to encrypt a number $M$, which represents a mesage (If $M>n$ then you break $M$ into segments each of them $<n$).

Each recipient has an encryption key $(n,k)$, with it we can encrypt $M$, BUT NOT decrypt due to a property that we will discuss in a moment. $n$ is equal to a product of two big primes ( $n=pq$), and $k$ is a random positive integer satisfying $gcd(k,\varphi (n))=1$ (preferably higher than both $p$ and $q$).

We get our encrypted message, $r$, by raising $M$ to the power of $k$ modulo $n$.

$M^k=r$ (mod $n$)

The receiver then decyphers the transmitted information by first determining the integer $j$, for which:

$kj=1$ (mod $\varphi (n)$)

Since $gcd(k,\varphi (n))=1$ this linear congruence has a unique solution modulo $\varphi (n)$. The Euclidean algorithm produces $j$ as a solution $x$ to the equation :

$kx+\varphi (n)y=1$

This equation can easily be solved once you know $\varphi (n)=(p-1)(q-1)$ [this can be proved very easily, if you need help, ask]

And in order for someone to know $\varphi (n)$ he must know $p$ and $q$ which composite $n$, and since we chose $p$ and $q$ to be very large prime numbers (let's say200 digits each) it is very unlikely that someone will find them given only $n$ with our current computer power.

Once the receiver found $j$ he simply has to calculate $r^n$ (mod $n$) to find $M$. Because $kj=1+\varphi (n)t$ for some integer $t$,

$r^j=(M^k{)}^j=M^{1+\varphi (n)t}=M(M^{\varphi (n)}{)}^t=M\times 1^t=M$ (mod $M$)

whenever $gcd(M,n)=1$ (which is a necessary condition in order for us to use Euler's theorem - regarding the phi function). It is highly unlikely that they are not relatively prime. But if they turn out not to be relatively prime we may use a similar argument that establishes $r^j=M$ (mod $p$) and $r^j=M$ (mod $q$ which yields the congruence $r^j=M$ (mod $n$).

Each person (Call him Steve) sends out a public key, namely $(n,k)$. Each person (John) that desires to encrypt a message to Steve uses this public key to encrypt a message and then sends it back to Steve. ONLY Steve can decrypt the message because only he knows $p$ and $q$.
I hope I explained it clearly enough If not (which is very likely) I'll be more than happy to explain.


Yatir

By Andre Rzym on Sunday, December 01, 2002 - 05:33 pm:

Taking a step back, there are two broad types of encryption algorithms: symmetric algorithms and public key algorithms .

With the former [example: DES], knowing the encryption key enables one to deduce the decryption key and vice versa. Security resides in keeping the encryption key safe.

With the latter [example: RSA, also try looking up PGP on the web] the encryption (public) key is freely given to anyone interested -knowing it is enough to encrypt a message but still not enough to decrypt the message. So I announce my public key on the web, you encrypt a message and send it to me. Only because I know something else (the private key) can I decrypt the message.

The use of primes arises from (some) public key algorithms. The idea is that it is easy to generate very large prime numbers (or at least very likely to be prime, so called 'industrial primes'). The product is, nevertheless, very difficult for someone to factor. Prime proving is easier than factoring. So I create two large primes and multiply them. I devise an algorithm for which encryption rests on the use of the composite number, and decryption is secure provided I cannot easily factor the number. So I announce the product to the world and keep the prime factors to myself. Anyone can now send me an encrypted message but only I can read it because only I have the factors.

If you want to read more, you might try 'Applied Cryptography' by Bruce Schneier.

Andre

The 'Handbook of Applied Crypography', is also a good introduction, and is available freely online.

It might be worth pointing out that Cryptography makes use of an extremely wide variety of mathematical disciplines like group theory, number theory, and probability theory to name but a few. For example, the current Advanced Encryption Standard, Rijndael, (the successor to the DES) treats bytes as elements of a finite field (viz. F_2⁸ ).

Bruce Schneier's company website, www.counterpane.com , has a lot of links to papers and websites on cryptography.

Kumusta! ~~~
Since you're interested in ENCRYPTION , maybe you'd like this: a site which features Data Encryption Techniques ...try this link...

http://www.mrp3.com/encrypt.html

Enjoy the site!