0
$\begingroup$

Disclaimer: I'm new to cryptography

Background: Clifford Cocks, the former GCHQ mathemetician and crytologist, gave an interview where he said:

"My thinking was that you need something that is easy to do, and difficult to undo, so I thought of the product of two primes. It's essential that you have a one-way function which can only be inverted if you know the factors — and raising numbers to a power with the product as modulus is something you can unpick only if you know the factors."

Question: Does anyone have a very simple example of this?

My (probably wrong) attempt:

$2^2 \times 2^3 = 32$ whose factors are $1,2,4,8,16,32$
$x^{32} = y$
$y$ modulo ?

$\endgroup$
1
  • 6
    $\begingroup$ He is referring to RSA, which is very common. You should be able to find countless tutorials and examples using your favourite internet search engine. $\endgroup$
    – yyyyyyy
    Apr 7 '16 at 12:03
3
$\begingroup$

I'll give a brief and simple example of what is described in the quote, which is now known as RSA for which there are plenty of descriptions and tutorials for all levels of understanding as pointed out by yyyyyyy.

... so I thought of the product of two primes ...

So, for our example this will be $p=21$ and $q=23$ of which the product is $n=21\times 23=483$. Note that you'll find it easy to multiply the two numbers to find $483$, but will have a rather hard time to find the factors of $483$, only given a calculator or pen and paper, for real-world encryption the primes will be around $10^{300}$.

... raising numbers to a power with the product as modulus...

For our example let's pick the exponent $e=17$, which is also sometimes used in the real-world. As our example message, let's pick $m=131$. You'd now raise $m$ to the power $e$ modulo $n$ ($=m^e\bmod n$). In our example this would mean calculating $131^{17}=985398793384554108247251712700460611$ (using a calculator or a math program may be useful here). Next, you'd apply the modulo operation which is taking the remainder of division with remainder. In our example this would mean calculating $985398793384554108247251712700460611\bmod 483$ which is $395$ -- your result -- as $395 + 483 \times 2040163133301354261381473525259752=985398793384554108247251712700460611$.

That's it what he actually described in his quote, I'll add the decryption procedure below.


For decryption you must find an integer $d$ such that $(e\times d) \bmod{((p-1)\times(q-1))} = 1$ (also commonly notated as $ed\equiv 1\pmod{\varphi(n)}$). Normally you use the extended euclidean algorithm to find this value efficiently. In our example $d=233$, which you can use as the exponent to which you need to raise the ciphertext in order to retrieve the original message. So you'd calculate $c^d\bmod n=395^{233}\bmod n=131$ (don't bother calculating $395^{233}$, it's over 500 digits long) and get $131$ as expected.

$\endgroup$
1
  • $\begingroup$ Very nice! Is this related to "a one-way hash" with a "trapdoor"? From Schneier's Applied Cryptography, "Mathematically, the process is based on the trap-door one-way functions previously discussed. Encryption is the easy direction. Instructions for encryption are the public key; anyone can encrypt a message. Decryption is the hard direction. It's made hard enough that people with Cray computers and thousands (even millions) of years couldn't decrypt the message without the secret. The secret, or trapdoor, is the private key. With that secret, decryption is as easy as encryption." $\endgroup$ Apr 8 '16 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.