This week at work has been really problematic. It all started when the filesystem of one of our servers which had fedora installed crashed. That was the beginning of a very long week. As a result i 've had to tinker with the transference of data between different linux servers, basically doing a copy of some critical root folders.
The copy was made throught a script in python and for each copy statement i needed to authenticate to the target server which nullifies the automatization of the script. This leads me to the topic of this post: i needed to authenticate automatically without password between the server sending the data and the one receiving it. After googling a bit, i found that RSA authentication was the way to go. When i was early at college i remember my father suggesting i read a book called "The Code Book" by Simon Singh. The author revisits the history of criptography in a very comprehensive manner and this book was the reason i took criptography as an optional subject at university (In spain, in order to complete the degree you usually have some "optional" different complementary subjects you get to choose to differentiate your academic itinerary. Anyways i dove into my library and rescued the book from the shelves.
I want this post to be a refresher/reminder of how the RSA works. But i'll start first by recalling how Whitfield, Hellman and Merkle solved the traditional problem of the key distribution which is the first step to the public/private key cypher.
WHITFIELD,HELLMAN & MERKLE: KEY DISTRIBUTION SOLVED
I will skip the personal descriptions the author makes in the book, yet interesting to get to know the men. I will get straight to the point, first with the analogy and then with the simple maths.
The cyclic problem with traditional criptography is that in order to send a cyphered message you need first to share the same key with the recipient, which leads to same problem again: how do i cypher the key with another key to be able the cypher the initial message?
Suppose Alice wants to send a message to Bob without Eve knowing, who in fact is listening. Alice the message written in a letter in a chest with a padlock which she owns the key and sends the chest to Bob.
What does Bob? He cannot unlock the chest because he doesnt own the key. This is the crutial fact in my opinion because traditionally all efforts at this point consisted of Bob trying to get Alice's key. On the other hand, Bob puts on the chest his own padlock and returns the chest back to Alice. Alice this time unlocks her padlock and removes it and sends again the chest. At this point, Bob receives the chest which he can open because he owns the key of the only padlock remaining.
If you understand the message sent as the "key" that can be used to cypher a message, Bob and Alice just shared the message using both their own different private key!!!!
It is worth noting that this implies that the order in which code must not matter, contrary to traditional cyphering. If one codes with key A and then codes the cyphered message again with key B, you must exactly follow the inverse order when decoding: first start by the last, decode with key B and then with key A. If you try to decode first with key A and then with key B it's pretty obvious you wont get the original message. In the idea explained before: it's Alice who first puts the padlock and then Bob but it's Alice the first to unlock (so to decode) in opposition to traditional coding rules (It should be first Bob to unlock since he was the last to lock up the chest)
Now the difficulty was obviuosly to translate this idea to something machines and computers could understand, and since they only understand 0s and 1s, numbers they needed to find a mathematical function with properties alike.
Mathematical functions are usually "two-way" which means you can revert the calculation, in other words: f(A) = B, then you can find g(x) such that g(B) = A. For example the doubling function has its counterpart when dividing by 2.
Whitfield, Hellman & Merkle concentrated on "one-way" mathematical functions and they found modular arithmetics field to be very rich in "one-way" functions. Take for example: 3 exp(x) [mod 11], for the firsts values of x=1,2,3,4,5,6... you have the following results: 3,2,6,4,5,1 which is pretty irregular. Let's see how this works:
This is how the problem of the key distribution in criptography was solved. Now it has still an inherent problem: since this solution is based on the communication between Alice and Bob it requires both to be "online". If Alice is in Boston and Bob is in Hawaii and she wants to send him a message immediately, Bob needs to be awake so they can share the same key, then Alice can send the message whenever she wants. But they both need to be awake and online first to set the cypher key. This will be solved by RSA public/private key.
Martin Hellman (left) and Whitfield Diffie (right)
RIVEST, SHAMIR & ADLEMAN: ASYMMETRIC CRYPTOGRAPHY
Like most of the great inventions in history, one breakthrough cannot be understood without the previouses ones in the field. The RSA (Rivest-Shamir-Adleman) public/private key was developped thanks to the idea of asymmetric cryptography invented again by Whitfield Diffie. Although Whitfield didn't have a clear concise idea of such a cypher. This is where those three men come in. After reading Whitfield's paper Rivest Shamir and Adleman started their quest to find such cypher.
But first: What is asymmetric criptography? So far, all the criptography was symmetric which means that both the receiver and the sender own the same information, this is: the same key to code and decode the message. Asymmetric cypher proposes that you use a key for coding the message and a different one for decoding.
Whitfield had imagined a system of pair of keys one public which everyone could find in a book such as the telephone guide used to encode the message for that recipient and another private one that only the recipient owns and that enables him to decypher the message coded with the public key. Whitfiled just didnt have a concrete example. After Whitfield published his paper in 1975 several mathematitians started the search for a special one-way function that could be inverted in restricted conditions, this is, when the recipient has a special information.
Rivest, Shamir and Adleman found what they were looking for. The RSA cypher relies on the difficulty to find the prime factors of a big number N. Alice can choose a number N big enough. how? by choosing first two prime numbers also big enough, then Alice sends this N number (her public key) to whoever wants to communicate with her but keeps p and q secret ( N = p x q). So Bob finds N in the telephone guide and encodes a message to Alice. Since Alice knows p and q (her private key) she can decypher the message... But what happens to Eve who is listening? Can't she deduce p and q knowing N? As stated it's far far very far easier to calculate how much is p x q than given N, get to know p and q, its prime factors.
What follows is an example of how the RSA works:
Rivest,Shamir & Adleman at the RSA time creation.
The strength of the RSA application of Whitfield's idea resides in that nowadays it's computationally very time-consuming to try to factorize N and hence discover p and q. The bigger the prime numbers, the bigger N and then more time needed to try to invert the one-way function. We are talking here of centuries given the large numbers. Mathematitians claim that discovering another way of factorizing in prime numbers other than the obvious one consisting of dividing N for each prime number p such that p < N is very difficult. They are quite convinced there must be a mathematical rule that states that's the only way of doing it. So until someone discovers a shortcut or computers become powerful enough to break RSA in a reasonable amount of time, RSA will still rule communications worldwide.
As for Whitfield Diffie and Martin Hellman they ve been awarded this year 2016 with the Turing Award by the Association for Computing Machinery (ACM).
Whitfield (left) and Hellman (right) nowadays.
RSA SERVER AUTHENTICATION
We ve explored how the RSA works and how one can send a private message to a person/institution/company. The recipient must own a pair of keys, one he makes public to everyone he wants to receive messages from and one private so he is the only one able to decypher it.
Well, there is another use of RSA that works just the contrary. Imagine you want to login to a server claiming you are who you claim to be. This time it's the sender, not the receiver who needs to generate the pair of keys. The sender keeps his private key secret and sends his public key to the server. So the sender cyphers the message with its private key and sends it the to the server he wants to authenticate. The receiver, because he owns the sender's public key can decypher the message.
Here is a diagram of a laptop trying to communicate with a server but the same process is valid for interservers communication.
1). Logon to server A. Type: ssh-keygen
The utility will prompt you to select a location for the keys that will be generated. By default, the keys will be stored in the ~/.ssh directory within your user's home directory. The private key will be called id_rsa and the associated public key will be called id_rsa.pub ,
2) Copy the id_rsa.pub public key to the target server B using:
cat ~/.ssh/id_rsa.pub | ssh username@remote_host "mkdir -p ~/.ssh && cat >> ~/.ssh/authorized_keys"
3) Now you can ssh from server A to B without being prompted for a password. In my case, i used it to start a script that copies between servers so i can do a :
scp -p /path/to/file username@remote_host:/path/to/
Sources & links:
- "The Code Book", by Simon Singh
- https://www.digitalocean.com/community/tutorials/how-to-configure-ssh-key-based-authentication-on-a-linux-server
- https://en.wikipedia.org/wiki/Public-key_cryptography
- http://www.nytimes.com/2016/03/02/technology/cryptography-pioneers-to-win-turing-award.html?_r=0
No hay comentarios:
Publicar un comentario