My little cousin (12year) asked me about how emails are encrypted and I want to answers her in such a way she understands it. This is diffuct, but I am happy with teaching the definition of a prime number and a composite.
Is there a teacher here who knows how to explain it in such a way that I and make her understand how to factor a number in to primes and what a prime number is?
On
Take six coins, candies, almonds, or something or that sort. Arrange them in a $3\times 2$ rectangle. Mix them up and ask your cousin to make them into a rectangle. Then do the same with eight coins and with nine. (9 is important! Otherwise she might think that prime means "odd"!) Do 12 if she hasn't lost interest yet.
(Let's say your cousin never tries arranging the items in a $1\times n$ line. Maybe she naturally won't consider this a rectangle. If she does, the pedagogy will change a little, but the main plan won't.)
Now give her 7 items to arrange in a rectangle. After a while she will discover that they cannot be arranged into a rectangle; there are always some left over.
Then you say:
“Some numbers, like 6 and 8, make rectangles. Others, like 7, don't. A prime number is a number that doesn't make a rectangle.”
If your cousin considers $1\times n$ to be a rectangle, that's all right. After she makes the $1\times 7$ rectangle, say “Yes, that's a special kind of rectangle called a ‘line’. Can every number make a line?” She will agree. “Can 7 items make a rectangle that isn't a line?” Then proceed as before: every number can make a line, and a prime is a number that can only make a line.
I don't know how to get from this to encryption though. If I were talking about encryption, I would omit the primes, which are not the main idea. The important idea is that there are two keys, one for scrambling and one for unscrambling, and you publish the scrambling key and keep the unscrambling one secret. The primes in the RSA and Diffie-Hellman methods are examples of the many ways of accomplishing this, and in fact the first published method of asymmetric encryption did not involve primes, but was based on solutions to the knapsack problem.
If what she really wanted to understand is how anything could be encrypted at all, I would take a completely different path. Show her how to add a secret key to a plaintext, adding each pair of letters mod 26, to get a ciphertext. For example, if the key is YOBGORGLE and the plaintext is THURSDAY, the sum is SWWYHVHK, where for example S = Y + T because $25+20\equiv 19\pmod{26}$.
Then someone who wants to decrypt the ciphertext and who knows the key can subtract the key from the ciphertext, again mod 26, to get the plaintext again.
On
Start listing the multiples of 2 and 3 and so on, marking them off on the number line, and say a prime is any number above 1 that can't be obtained by multiplying any two numbers except itself with 1 - that is, the numbers that start each different sequence like counting by 2s and 3s.
Given her age, I tried an introduction to the basic properties of modular arithmetic and how it gets into cryptography instead. I will not be held liable for any damages that may be incurred by trying to teach abstract algebra to a 12 year-old, however I'll be happy to assist with technical support. Note that computing remainders is standard elementary school curriculum in the U.S.:
Teach multiplication on a 12-hour clock first, til she gets the hang of it. Then point out that 3*4=0 is an unusual property for a number system. Then ask what the numbers are where a clock of that size will behave normally, and not have two numbers' product be 0 unless one of them is 0.
Now try the Caesar cipher. In the case of the Caesar cipher, to encrypt it you need to pick some number of letters to shift by, and that same number of letters is what you need to know to decrypt it. But if you want to encode a message with the same code each time, but send a message to different people, you need the information you need to decode it to be different from the information you need to encode it. But how do you build such a thing?
[The next two paragraphs could be skipped, or the explanation could end with the next paragraph.]
Give her an exponent $b$ and the last digit of $a^b$, and ask her to find $a$ by looking on the (2-1)*(5-1)-hour clock for a number $d$ such that $bd$ is $1$ on that clock. At this stage you'd have to write down the multiplication table. It will happen that in taking the last digits of $2^d, 3^d, ...$, one eventually gets a number that, magically, is $a$. Clearly the encoding process is not the same as the decoding process. But it's not at all clear why this works, so the long answer is to give a a bit deeper an understanding of how you make a clock.
Suppose John and Robert are the same person, and Robert and Tim are the same person. Then John and Tim are the same person. Now suppose you have three fruit. None of them are the same fruit, but you can use a similar structure to group the fruit together. If two of the fruits $a$ and $b$ are the same kind of fruit, and $b$ and the third fruit, $c$, are the same kind of fruit, then we assume all three fruit are the same kind of fruit.
Well, you can do the same thing with numbers, making even and odd numbers, for example. But there's something extra about even and odd numbers, because if even numbers are added together, you get an even number, two odd numbers get you an even number, and so on. Those rules weren't imposed, they were found out. What do they say? That if two numbers $a$ and $b$ are of the same type, then the sums $a+c$ and $b+c$ are of the same type, no matter what $c$ is. Incredibly special! Now, if you were just looking to find a list of all the different types of fruit, you would think of two apples as being the same thing, and ignore every apple beyond the first one you saw. So let's start from 0 and ignore all even and odd numbers beyond the first one we see. 0 is even, and 1 is odd, but then 2 is even again. So 1+1=2 becomes 1+1 is the same type as 0. 1+0 is the same type as 1, and so on. If you take the addition table for even and odd numbers, and the addition table for the 0 and 1, they're the same.
Now, on a number line, as an experiment, ask her to see what happens if all you do is say that 0 and 3 are the same type of number, and that if $a$ and $b$ are of the same type, then the sums $a+c$ and $b+c$ are of the same type, no matter what number $c$ is. You can color the numbers by their types, or just write the first number of that type underneath it. What you'll see is that every number gets one of three types, and the pattern is repeating. If you think of them as all the same thing when they're the same type, you'd just be coiling the number line up into a circle. The number of points on the circle is the number you chose to say was the same type as 0.
Now take the 12-hour clock, and impose the same rule about adding types, but pick a number not equal to 0, declare it to be the same type as 0, and see how the rules still assign everything a type. But how many types, exactly?
I think the best way to explain encryption is something like this:
Imagine you want to safely send a package to me, without taking any chances it will get stolen in transit. First, mail be a box with an open lock in it. I'll take my own open lock, put it inside the box, then lock the box with your lock and mail it back to you. (Call me to confirm you did this -- that's how I know I'm not just getting a lock from someone else who stole the box when it was in the mail.) When you receive the package, unlock your lock, take out mine, put what you want to mail to me inside, then lock it with my lock and send it back to me.
(This isn't a direct analogy for how things are really done, but it explains the basic principle that by being clever with how locks are transported you can transmit something securely.)
Now, the thing that makes this work is a special feature of a lock: anyone can put a lock on if it's open, but once it's on you need the key to get it off.
If we want to do this with computers, we have to come up with a math problem that works that way: it's easy to do it in one direction, but once it's been done it's hard to undo unless you know something special (the key).
Okay, so suppose I give you two numbers, say 23 and 47, and asked you to multiply them together. You know how to do that, right? You just write them down, multiply 3 times 7, [etc.] and you get 1081. On the other hand, what if I told you I multiplied two numbers together and got 1081, and I asked you what the numbers were? Well, you know now -- they're 23 and 47. But if you didn't know that, how would you figure that out? You'd just have to try every pair of numbers until you figured it out. I mean, maybe you could be a little clever about it, but it'd still be hard work no matter what you did.
So multiplying two numbers together is like closing a lock, and getting the numbers back is like trying to open it.
(Again, this doesn't really quite agree what we really do when we encrypt a message, but it gets the principle of a one-way function across and segues nicely into talking about prime numbers.)
Now that you've (hopefully) motivated the problem of trying to factor an integer, you have a good place to start talking about primes -- they're just the point at which you can't factor any further and so you're done.