Hi, so I decided that, as i have the entire week to my self i will put in an introduction to Cryptography, for all who are interested in the subject. I will be updating the post, for the next week with new information and sections on cryptography.
Okay, before we move into the real interesting subjects of cryptography like, key exchange protocols, signatures, certificates, Symmetrical cryptography and Asymmetrical cryptography, hash fictions, and prime numbers. We will first look into the history of cryptography and its origins.
History of the Hidden Language.
During ancient times, when leaders and generals needed to send messages to their troops, with instructions on what they should do. It was very easy for the enemy to intercept those messages , by ambushing supply routs (in modern time its equivalent is the man in the middle attack), So this meant the message was easily read and the enemy would know what the other side was planning. to prevent this from happening there was only two ways of preventing this from happening, First, was to hide the message so that it looks just like a normal every day thing (Steganography). Steganography the art of hiding messages so that it is only known to the person receiving the message that a message is hidden in it, a good example is invisible ink. Now, the Second way was to make the message unreadable for any person who was not the intended recipient. And this is what many did, because unlike stenography encryption could be taught to people easily and could be done with much less resources. so In a war situation teaching generals and messengers how to put cryptography was much more efficient.
Early encryption techniques were rather simple and you yourself may have played with it when you were kids.
Two main cipher system used were:
Transposition cipher
Substitution ciphers
A Transposition cipher uses a very simple method of encryption one of the most popular ones were the scytale, basically the scytale is a piece of wood, on which a strip of paper is wounded up to revel what message. so the person sending the message to some one would have an identical scytale as the other and would wind the paper on it and write the message then unwind the paper and fill the empty space with random words. if another person intercepted the message and used a different size scytale the message would not show.
Problem with this was the sender and the receiver required identical scytale.
A Substitution ciphers is another simple cipher that substituted the actual alphabets with some other alphabets or numbers. The Caesar Cipher is by far the most famous of them all, used a simple shift technique to substitute the alphabets, Used by Caesar himself and the roman empire Eg bellow.
Three shift right →
Plain: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cipher: X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Planetext - Bitcoin is a crypto coin
Ciphertext- Efqzlfk fp x fovmql flfk
Notice there is repetition of the same alphabets that have been substituted.
So, looking at the cipher above you can now encrypt any length of message through substitution, and all the receiver has to know when receiving the message is how many shifts are used.
However all these methods are venerable to cryptanalysis techniques, like a frequency analysis. All a person has to do is count the alphabets and make a note of each of the alphabets and the number of times it appears. In the english language some alphabets appear more that some, using this, we can determine which symbol or alphabet was replaced.
Polyalphabetic cipher
Due to the ease of all these Cipher being broken a new system was requires, one which could not be so easily broken using a frequency analysis. many new ciphers came in and out. One being predominantly used for hundreds of years was the Polyalphabetic cipher on which normal frequency analysis attack method did not work. and it used a key. The Vigenère cipher the best known of them all and its harder cousin Autokey cipher remained one of the most used ciphers during the 15th and the 16th and up to mid 18th century, remained unbroken.
It was a variant of a Substitution ciphers but with multiple shifts and alphabets and also the use of a key made it versatile and impenetrable.
This is how a Vigenère cipher looks like.
Eg:-
Message - TO BE OR NOT TO BE THAT IS THE QUESTION
KEY - RELATIONS
Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL
Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION
Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
Notice there is no repetition of the same alphabets that have been substituted .
This kind of ciphers remained active for many hundreds of years and was used widely in Europe and the middle east. However the fate of this cipher system was doomed, when a brilliant man who we all know and admire in the computing world came along, the father of computer Charles Babbage, he broke both the Vigenère cipher and the much harder Autokey cipher.
Tomorrow we will touch upon mechanical ciphers, used in the second world war and then enter the world of modern cryptography, in the digital age.
The Rise of the Machine
The era of the second world war, was the proving grounds for modern encryption methods, ideas and innovation. In my opinion, if it was not for the Mathematicians, code-breakers and revolutionary thinkers, the modern computer age, the internet and space travel would not have been possible at all. The birth of computing devices, to conduct tasks through programmed inputs were all tested and innovated, by codebreakers trying to break the German Enigma code. The use of early computers was at England, in a place called Bletchley park. In fact, the first discovery of modern public key encryption system and early experiments on One Time Pads was done during this time.
Enigma Machine *Germany*(Left) | SIGABA *USA* (Middle) | TypeX *UK*(Right)
During the War the Germans used one of the most successful, mechanical crypto systems called the Enegma machine, it was a rotor cipher machine, similar to a Polyalphabetic cipher but with the difficulty increased by the rotor, if the allies broke the code all the germans did was change the configuration and may be add rotors giving another huge headache for code-breakers.
The US and the UK also used similar machine called the SIGABA and the TypeX. However, a code system that was never broken by the enemy was not mechanical at all, but were the Navajo code talkers who played a vital role in the success in the pacific war theater. There's even a movie called the Windtalkers played by Nicolas Cage although it concentrated more on the nipless cage than the Code talker.
Modern Cryptography
With progress happening in the Cryptography community one of them was by far the most revolutionary, the public key crypto system, the RSA algorithm that allowed people to have two keys one public and one private. this solved many problems of key transfer and security and validity of a encrypted message. This algorithm was already made during the second world war, but was classified. Until 1977 when a group in MIT rediscovered this algorithm on their own, hence the name RSA algorithm, the first alphabet of their surname Ron Rivest, Adi Shamir, and Leonard Adleman.
The advent of modern cryptography gave rise to secure communication, safe banking transaction, and greater communication, and social revolution. We use some form of encryption every day and sometimes we don’t even know that encryption is being used.
Cryptography, before the dawn of the Information age was confined to the intelligence community, with many of the technology kept classified and inaccessible to the general public. It was nearly impossible for a person without a connection to the intelligence community, or a large corporation like IBM to do any work on Cryptography. But, that all changed when the internet was born. People from around the world collaborated to bring cryptography to the masses. With the advent of the internet people were able to disseminate information about cryptography, and develop software for everyone to use.
This shift in knowledge from an intelligence based community to a worldwide public community, gave rise to many social changes. With people openly advocating the use of encryption to promote privacy, Bring down corrupt government, safeguard whistleblowers. During the late 80's many BBS's hosted score of text files relating to cryptography and around the early 90's a cypher punk mailing list was started, the birthplace of the cyberpunks, with the major discussion on technical issues, alternative uses of cryptography privacy, government surveillance, freedom of speech, civil society, and related issues. There have been many influential individual who have shaped this movement Eric Hughes, Jim Bell, Philip Zimmermann, Julian Assange just to name a few.
The roots of bitcoin can be traced back to the early discussion, within the cyberpunks and the cryptoanarchistic groups for an anonymous banking system. May be Satoshi Nakamoto might be one of the early cypherpunks, who was able to solve the problem of anonymous banking. But, we shall never know.
Cryptography has now become an integral part of our lives, in this modern day society it is rare not to come across technology that does not utilize some sort of encryption. I believe that the future for Cryptography is bright, because this is the only thing that can solve many of the world problems of secure communication, Tyrannical governments, greedy Banks, and immoral super corporations.
Tomorrow we shall finally talk about the technical part of modern Cryptography. Thinking about what to talk about tomorrow . I am a bit torn about where to start this from, and after a cigarette break I have decided to start with the basis of modern cryptography, the math’s behind it, so the topic for tomorrow would be Prime number related math’s, and will touch upon a Diffie and Hellman key exchange protocol.
The Numbers Game
The building blocks of every thing in maths my opinion is and always, the prime number. This number can form so many different numbers of any length, and a number of a particulate digit can be factorized to a smallest number being prime.
What is a prime number?
A prime number is a number divisible by it self and one. (basic old school definition)
take it this way, a number which cannot be divided equally without creating fractions of it.
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71...............
so, lets take for example an integer which Factorizes to
56984 = 2 × 2 × 2 × 17 × 419
What is prime factorization?
Prime factors of a positive integer are the prime numbers that divide that integer exactly like the example above.
So why is this useful to cryptography and online security?
Well the simple fact is that, it is easy to multiply two large prime numbers, but while trying to find the prime factor of that integer become a tedious task taking alot of time
a simple example like.
7703 × 6421 = 49460963
the output a compost number is going to take a long time to be factored, the example above may not be the best example of a large prime number being used but just Imagine a prime number P1 and P2 both the length of about 100 digits long or much longer and multiply those tow together the composite number would be hard to factorize the limit being the time taken to compute the result.
g mod p
42 mod 12 = 10
Working with prime modulus.
3^29 mod 17 = 12
so here calculating this makes it easy when we have the generator as 3 raised to the power 29 . However when we have the result as 12 and need to find 3 raised to the power x . this becomes a time consuming task.
3^x mod 17 = 12
This problem is also know as a discrete logarithm problem. Therefor this creates a One way function. easy to compute harder to decipher.
Therefore, if the size of the prime increases the time taken for a computer to compute the result of that, would take a very long time.
Clock arithmetic :
If we consider prime numbers as the ingredients in our encryption recipe, the modular arithmetic is utensil for cooking it up. we shall see a simple use of [ mod ] in a few examples while talking about the Key exchange protocol especially the Diffie and Hellman key exchange protocol.
Lets take an example of two people who are honest employees in a corrupt government service, Alice and Bob, and lets take for example their Evil boss is Eve.
Alice and Bob want to communicate with each other but, does not want any one to read their messages, as they know Eve would most likely be reading their emails.
so how would the two communicate without Eve being able to read their messages.
Firstly, Alice and Bob has to agree on a secret key so that they can use that key to encrypt messages and send to each other but, the problem is that if they send the key without encrypting it , Eve would know what the key is and can read all the messages Alice and bob send each other. This is where the Diffie and Hellman key exchange protocol would be most useful.
So how does it work?
Alice and Bob agree on a generator and a prime modulus.
g = 3
p = 17
What Alice does :-
She chose a random number
and then raises that on the generator, result q = 15
g^x mod p = q
3^54 mod 17 = 15
Alice, then sends this result 15 over the insecure line to Bob
What Bob does
He chose a random number Bob.
and then raises that on the generator, result r = 16
g^y mod p = r
3^24 mod 17 = 16
Bob, then sends this result 16 over the insecure line to Alice
What Alice does is,
uses Bob's result as a generator raised to the power of the random number Alice chose to calculate a secret key s
r^x mod p = s
16^54 mod 17 = 1
Bob also does the same thing using the number Alice sent Bob. to generate a secret key
q^y mod = p = s
15^24 mod 17 = 1
Here Both Bob and Alice was able to compute the secret key s without transmitting the key over the insure line.
Meanwhile, Eve who is reading the messages coming in, can only intercept the following details from Bob and Alice
the generator 'g', prime modulus 'p' and the two results of the calculation by Alice and Bob 'q' and 'r'.
What Eve is missing is the private numbers that Alice and Bob used to generate the Secret 's' . without the 'x' and 'y', it is impossible for Eve to determine what secret key Alice and Bob is using to encrypt their messages.
Alice '(m)' → Bob
s(m) s(m)
So, here Alice sends Bob an encrypted message using a secret key 's', which Bob then uses the Secret key 's' to decrypt the message Alice Sent him.
As you can see with this protocol many of the problems of secret key transfer is solved. This also leads us to the path of asymmetrical encryption and the use of the later RSA algorithm's public key cryptosystem to encrypt messages.
I hope this was simple to understand, i tried to put in as much details without making it confusing, i hope you all like it and understand. Next, i will cover the public key cryptosystem namely the RSA algorithm, and then touch upon Hashing, one time pads and a few single key encryption on block ciphers.
By subvolatil of Bitcoin Talk Forum!
Original Thead at https://bitcointalk.org/index.php?topic=246307
Okay, before we move into the real interesting subjects of cryptography like, key exchange protocols, signatures, certificates, Symmetrical cryptography and Asymmetrical cryptography, hash fictions, and prime numbers. We will first look into the history of cryptography and its origins.
History of the Hidden Language.
During ancient times, when leaders and generals needed to send messages to their troops, with instructions on what they should do. It was very easy for the enemy to intercept those messages , by ambushing supply routs (in modern time its equivalent is the man in the middle attack), So this meant the message was easily read and the enemy would know what the other side was planning. to prevent this from happening there was only two ways of preventing this from happening, First, was to hide the message so that it looks just like a normal every day thing (Steganography). Steganography the art of hiding messages so that it is only known to the person receiving the message that a message is hidden in it, a good example is invisible ink. Now, the Second way was to make the message unreadable for any person who was not the intended recipient. And this is what many did, because unlike stenography encryption could be taught to people easily and could be done with much less resources. so In a war situation teaching generals and messengers how to put cryptography was much more efficient.
Early encryption techniques were rather simple and you yourself may have played with it when you were kids.
Two main cipher system used were:
Transposition cipher
Substitution ciphers
A Transposition cipher uses a very simple method of encryption one of the most popular ones were the scytale, basically the scytale is a piece of wood, on which a strip of paper is wounded up to revel what message. so the person sending the message to some one would have an identical scytale as the other and would wind the paper on it and write the message then unwind the paper and fill the empty space with random words. if another person intercepted the message and used a different size scytale the message would not show.
Problem with this was the sender and the receiver required identical scytale.
A Substitution ciphers is another simple cipher that substituted the actual alphabets with some other alphabets or numbers. The Caesar Cipher is by far the most famous of them all, used a simple shift technique to substitute the alphabets, Used by Caesar himself and the roman empire Eg bellow.
Three shift right →
Plain: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cipher: X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Planetext - Bitcoin is a crypto coin
Ciphertext- Efqzlfk fp x fovmql flfk
Notice there is repetition of the same alphabets that have been substituted.
So, looking at the cipher above you can now encrypt any length of message through substitution, and all the receiver has to know when receiving the message is how many shifts are used.
However all these methods are venerable to cryptanalysis techniques, like a frequency analysis. All a person has to do is count the alphabets and make a note of each of the alphabets and the number of times it appears. In the english language some alphabets appear more that some, using this, we can determine which symbol or alphabet was replaced.
Polyalphabetic cipher
Due to the ease of all these Cipher being broken a new system was requires, one which could not be so easily broken using a frequency analysis. many new ciphers came in and out. One being predominantly used for hundreds of years was the Polyalphabetic cipher on which normal frequency analysis attack method did not work. and it used a key. The Vigenère cipher the best known of them all and its harder cousin Autokey cipher remained one of the most used ciphers during the 15th and the 16th and up to mid 18th century, remained unbroken.
It was a variant of a Substitution ciphers but with multiple shifts and alphabets and also the use of a key made it versatile and impenetrable.
This is how a Vigenère cipher looks like.
Eg:-
Message - TO BE OR NOT TO BE THAT IS THE QUESTION
KEY - RELATIONS
Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL
Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION
Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
Notice there is no repetition of the same alphabets that have been substituted .
This kind of ciphers remained active for many hundreds of years and was used widely in Europe and the middle east. However the fate of this cipher system was doomed, when a brilliant man who we all know and admire in the computing world came along, the father of computer Charles Babbage, he broke both the Vigenère cipher and the much harder Autokey cipher.
Tomorrow we will touch upon mechanical ciphers, used in the second world war and then enter the world of modern cryptography, in the digital age.
The Rise of the Machine
The era of the second world war, was the proving grounds for modern encryption methods, ideas and innovation. In my opinion, if it was not for the Mathematicians, code-breakers and revolutionary thinkers, the modern computer age, the internet and space travel would not have been possible at all. The birth of computing devices, to conduct tasks through programmed inputs were all tested and innovated, by codebreakers trying to break the German Enigma code. The use of early computers was at England, in a place called Bletchley park. In fact, the first discovery of modern public key encryption system and early experiments on One Time Pads was done during this time.
Enigma Machine *Germany*(Left) | SIGABA *USA* (Middle) | TypeX *UK*(Right)
During the War the Germans used one of the most successful, mechanical crypto systems called the Enegma machine, it was a rotor cipher machine, similar to a Polyalphabetic cipher but with the difficulty increased by the rotor, if the allies broke the code all the germans did was change the configuration and may be add rotors giving another huge headache for code-breakers.
The US and the UK also used similar machine called the SIGABA and the TypeX. However, a code system that was never broken by the enemy was not mechanical at all, but were the Navajo code talkers who played a vital role in the success in the pacific war theater. There's even a movie called the Windtalkers played by Nicolas Cage although it concentrated more on the nipless cage than the Code talker.
Modern Cryptography
With progress happening in the Cryptography community one of them was by far the most revolutionary, the public key crypto system, the RSA algorithm that allowed people to have two keys one public and one private. this solved many problems of key transfer and security and validity of a encrypted message. This algorithm was already made during the second world war, but was classified. Until 1977 when a group in MIT rediscovered this algorithm on their own, hence the name RSA algorithm, the first alphabet of their surname Ron Rivest, Adi Shamir, and Leonard Adleman.
The advent of modern cryptography gave rise to secure communication, safe banking transaction, and greater communication, and social revolution. We use some form of encryption every day and sometimes we don’t even know that encryption is being used.
Cryptography, before the dawn of the Information age was confined to the intelligence community, with many of the technology kept classified and inaccessible to the general public. It was nearly impossible for a person without a connection to the intelligence community, or a large corporation like IBM to do any work on Cryptography. But, that all changed when the internet was born. People from around the world collaborated to bring cryptography to the masses. With the advent of the internet people were able to disseminate information about cryptography, and develop software for everyone to use.
This shift in knowledge from an intelligence based community to a worldwide public community, gave rise to many social changes. With people openly advocating the use of encryption to promote privacy, Bring down corrupt government, safeguard whistleblowers. During the late 80's many BBS's hosted score of text files relating to cryptography and around the early 90's a cypher punk mailing list was started, the birthplace of the cyberpunks, with the major discussion on technical issues, alternative uses of cryptography privacy, government surveillance, freedom of speech, civil society, and related issues. There have been many influential individual who have shaped this movement Eric Hughes, Jim Bell, Philip Zimmermann, Julian Assange just to name a few.
The roots of bitcoin can be traced back to the early discussion, within the cyberpunks and the cryptoanarchistic groups for an anonymous banking system. May be Satoshi Nakamoto might be one of the early cypherpunks, who was able to solve the problem of anonymous banking. But, we shall never know.
Cryptography has now become an integral part of our lives, in this modern day society it is rare not to come across technology that does not utilize some sort of encryption. I believe that the future for Cryptography is bright, because this is the only thing that can solve many of the world problems of secure communication, Tyrannical governments, greedy Banks, and immoral super corporations.
Tomorrow we shall finally talk about the technical part of modern Cryptography. Thinking about what to talk about tomorrow . I am a bit torn about where to start this from, and after a cigarette break I have decided to start with the basis of modern cryptography, the math’s behind it, so the topic for tomorrow would be Prime number related math’s, and will touch upon a Diffie and Hellman key exchange protocol.
The Numbers Game
The building blocks of every thing in maths my opinion is and always, the prime number. This number can form so many different numbers of any length, and a number of a particulate digit can be factorized to a smallest number being prime.
What is a prime number?
A prime number is a number divisible by it self and one. (basic old school definition)
take it this way, a number which cannot be divided equally without creating fractions of it.
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71...............
so, lets take for example an integer which Factorizes to
56984 = 2 × 2 × 2 × 17 × 419
What is prime factorization?
Prime factors of a positive integer are the prime numbers that divide that integer exactly like the example above.
So why is this useful to cryptography and online security?
Well the simple fact is that, it is easy to multiply two large prime numbers, but while trying to find the prime factor of that integer become a tedious task taking alot of time
a simple example like.
7703 × 6421 = 49460963
the output a compost number is going to take a long time to be factored, the example above may not be the best example of a large prime number being used but just Imagine a prime number P1 and P2 both the length of about 100 digits long or much longer and multiply those tow together the composite number would be hard to factorize the limit being the time taken to compute the result.
g mod p
42 mod 12 = 10
Working with prime modulus.
3^29 mod 17 = 12
so here calculating this makes it easy when we have the generator as 3 raised to the power 29 . However when we have the result as 12 and need to find 3 raised to the power x . this becomes a time consuming task.
3^x mod 17 = 12
This problem is also know as a discrete logarithm problem. Therefor this creates a One way function. easy to compute harder to decipher.
Therefore, if the size of the prime increases the time taken for a computer to compute the result of that, would take a very long time.
Clock arithmetic :
If we consider prime numbers as the ingredients in our encryption recipe, the modular arithmetic is utensil for cooking it up. we shall see a simple use of [ mod ] in a few examples while talking about the Key exchange protocol especially the Diffie and Hellman key exchange protocol.
Diffie and Hellman key exchange protocol
Problem of Exchanging Keys :-Lets take an example of two people who are honest employees in a corrupt government service, Alice and Bob, and lets take for example their Evil boss is Eve.
Alice and Bob want to communicate with each other but, does not want any one to read their messages, as they know Eve would most likely be reading their emails.
so how would the two communicate without Eve being able to read their messages.
Firstly, Alice and Bob has to agree on a secret key so that they can use that key to encrypt messages and send to each other but, the problem is that if they send the key without encrypting it , Eve would know what the key is and can read all the messages Alice and bob send each other. This is where the Diffie and Hellman key exchange protocol would be most useful.
So how does it work?
Alice and Bob agree on a generator and a prime modulus.
g = 3
p = 17
What Alice does :-
She chose a random number
and then raises that on the generator, result q = 15
g^x mod p = q
3^54 mod 17 = 15
Alice, then sends this result 15 over the insecure line to Bob
What Bob does
He chose a random number Bob.
and then raises that on the generator, result r = 16
g^y mod p = r
3^24 mod 17 = 16
Bob, then sends this result 16 over the insecure line to Alice
What Alice does is,
uses Bob's result as a generator raised to the power of the random number Alice chose to calculate a secret key s
r^x mod p = s
16^54 mod 17 = 1
Bob also does the same thing using the number Alice sent Bob. to generate a secret key
q^y mod = p = s
15^24 mod 17 = 1
Here Both Bob and Alice was able to compute the secret key s without transmitting the key over the insure line.
Meanwhile, Eve who is reading the messages coming in, can only intercept the following details from Bob and Alice
the generator 'g', prime modulus 'p' and the two results of the calculation by Alice and Bob 'q' and 'r'.
What Eve is missing is the private numbers that Alice and Bob used to generate the Secret 's' . without the 'x' and 'y', it is impossible for Eve to determine what secret key Alice and Bob is using to encrypt their messages.
Alice '(m)' → Bob
s(m) s(m)
So, here Alice sends Bob an encrypted message using a secret key 's', which Bob then uses the Secret key 's' to decrypt the message Alice Sent him.
As you can see with this protocol many of the problems of secret key transfer is solved. This also leads us to the path of asymmetrical encryption and the use of the later RSA algorithm's public key cryptosystem to encrypt messages.
I hope this was simple to understand, i tried to put in as much details without making it confusing, i hope you all like it and understand. Next, i will cover the public key cryptosystem namely the RSA algorithm, and then touch upon Hashing, one time pads and a few single key encryption on block ciphers.
By subvolatil of Bitcoin Talk Forum!
Original Thead at https://bitcointalk.org/index.php?topic=246307
