A task for cryptography basics with a detailed analysis
Here is the task through which you can briefly become familiar with the basics of RSA-cryptography.
Let’s suppose you want to make sure that your friend John has your phone number. However, you cannot ask him directly. You will have to write him a message on the card and give the card to Kate, who will act as an intermediary. Kate will carry the card to Petya, he will write a message and give it to Kate, and then she will bring it back to you. However, you do not want Katya to know your phone number. Thus, here is the question: how should you formulate the question to John under existing conditions?
Even if you find a short and simple answer, you may be asked to provide an answer based on RSA. It is not so tough in case John has a PC and he follows your recommendations. Ask an interviewer how John is good at PC and math.
While using RSA, two keys are generated: public and private. A public key is similar to an email. It allows any person to send you a message. A private key is something similar to your password for an email. You require it in order to get your emails and you should keep it secret. Otherwise, a message sent to you may be read by any other person.
You cannot send John a secret message as he did not create his secret keys. He may even do not know what RSA is and he will not know about it until you tell him about it. You want John to send you such a message, namely your telephone number. It means you need keys for yourself, not for John. Here is the common solution scheme.
“Hi, John. We are going to use the RSA cryptography. Maybe you even do not know what it is, but I will tell you what you need to do. Here is my public key… Take it and my telephone number and find out an encrypted number following the instructions. Send this encrypted number me back through Kate.”
The main goal is to create such instruction so that any person can use it. Moreover, you need to provide the required accuracy.
RSA cryptography was first created in 1973. The first RSA author was the British mathematician Clifford Cock, who then worked in the secret service of Queen Elizabeth II. In those years, his scheme was considered impractical: it required a computer. In those days, when spies usually managed with cameras hidden in cufflinks, this difficulty was not so easy to overcome. Until 1997, the idea of Coca was considered a secret. However, in 1978, three scientists from MIT, Ronald Rivest, Adi Shamir and Leonard Adleman, proposed it independently of Kok. The first letters of their last names (RSA) became an acronym and the name of this algorithm.
In the RSA system, a person who wants to receive messages should pick two random prime integer p and q. The numbers should be big, or at least they should be as big as the numbers and messages that you need to send. For a telephone number of 10 integers, both p and q should also include at least 10 numbers.
One of the ways to choose p and q is to use Google and find a website where big and prime numbers are specified. Let us say Prime Pages led by Chris Caldwell from the University of Tennessee at Martin. Randomly select two ten-digit primes. Here is an example of such a couple:
1 500 450 271 и 3 367 900 313.
Name them p and q respectively. You will have to multiply them and get the exact answer. There may be a slight difficulty since you will not be able to use calculators, Excel or Google, and most other consumer programs as they show a limited number of significant digits. One of the solution options is to multiply the numbers manually. Another solution option is to use Wolfram Alpha. Input
1 500 450 271 и 3 367 900 313
and you will get an accurate answer:
5 053 366 937 341 834 823.
Let’s name this product N. It is one of the components of your public key. The other component is a number, called e, arbitrarily chosen and equal in length, ideally N, but which is not exactly divisible by the product (p – 1) (q – 1). I may have confused you with the last sentence, but it does not matter at this stage.
In many application programs, cryptographers choose a simple trio as e. This is a good and sufficient option for many purposes and allows you to quickly encrypt the data.
You have received N and e, you now have everything you need to solve the task. You just need to send these two numbers to John, as well as a complete “Guide for Dummies for RSA cryptography.” John needs to calculate
хe mod N,
where Х is a telephone number. Due to the fact that we chose 3 as e, the part on the left is x, which is cubed. This will be a 30-digit number. “Mod” refers to the division by module, which means that you divide x³ by N and take only the remainder. This residue should be in the range from 0 to N – 1. It is likely that there will be a number of 20 digits. This number is an encrypted message that John will send back to you.
In order to solve this task, John will need to cube the number and make a division. An important part of the instruction may be the following.
“John, I want you to carefully follow these instructions and be sure. Assume that my phone number is a normal ten-digit number. First, it is necessary that you bring this number into a cube (first multiply it by itself, and then multiply the resulting product once more by the original number). The answer will be a 30-digit number, and it should be accurate. Perform this multiplication, even if you have to do it manually, and double-check it. Then you need to carry out the longest division process in your entire life. Divide the result by 5 053 366 937 341 834 823. It’s important not to be mistaken! Only the rest of this division send to me. It is important that you do not send the whole part, but only the remainder.”
Suppose that John has access to the Internet, then we write the following:
“John, you need to visit the website and www.wolframalpha.com. You will see there a long rectangle with borders painted in orange. Enter my 10-digit phone number into this box without any hyphens, periods or brackets, only ten digits. Immediately after the phone number, type the following
^3 mod 5053366937341834823.
Then click on the small equal sign located on the right side of the rectangle. The answer will probably be a 20-digit number that will appear in the box with the word Result. Send me this answer only.”
Surely, Katya will read these instructions, as well as read John’s answer. However, she cannot understand it. She received a number of 20 digits, which, as she knows, is the remainder of the cube of the telephone number divided by 5053366937341834823, modulo. No one has yet come up with an effective way to restore the original number from the remainder, in this case, a phone number.
Can you provide something better? Yes, because you have a secret decrypt key. It is d, Это d, an inverse value of e mod (p – 1) (q – 1). There is a convenient algorithm for its calculation, which you can use provided that you know two prime numbers p and q, which were used to obtain N.
State encrypt number/message which John has sent you back. Y. Its initial message was
Yd mod N.
In order to determine this value, you just need to enter in Wolfram Alpha (replace Y, d and N with actual numbers).
Kate knows N because it was written on a card that you asked here to send to John. She knows Y as it was specified in the response sent to John. However, she does not know d and she cannot define it. This way, Kate faces an algorithm difficulty. When you multiply two numbers, no one will have any difficulties, because this is what everyone in the school has taught. However, it is much more complicated to determine the multiplier, having a huge number.