Welcome back to the Year of Security! This is Week 2 of Module 2 : Modern Cryptography.
Week 1 covered classical ciphers and different types of encodings (which, as stated, is not a cipher but very useful for describing data in different ways, specifically integers which can be then utilised in other encryption schemes). However, now you enter the realm of modern cryptography. The schemes usually involve a series of mathematical steps to encrypt the data using key (or keys) to get the ciphertext, which once received by the receiver, would have to go through another set of mathematical steps to get the data using same or different key depending on what type of algorithm was used. (see https://en.wikipedia.org/wiki/Symmetric-key_algorithm and https://en.wikipedia.org/wiki/Public-key_cryptography).
One question comes to mind, how are these safe? After all, these are based on mathematics, and problems in mathematics get solved all the time!
Trying to formulate an attack for the scheme will often result in a compute-intensive problem. Of course, given enough computation power and time, you can technically break all the algorithms. However, there are many cases that the data can be found fast and in an appreciable time, mostly owing to people chosing vulnerable numbers. So yes, given any compute-intensive problem, you can even frame your own scheme!
(example of Diffie–Hellman key exchange, one of the first public-key protocols)
During any programming course, you must've come through the following logical operators (using C++ synthax):
- AND
a && b - OR
a || b - NOT
!a
Note that these operators worked with groups of bytes and gave a boolean output.
Now, there is something called 'bitwise operators' which work on the bits within the byte. The calculation performed on bits is just like that of logical operators. They take inputs as an integer and return an integer. These are:
- AND
a & b - OR
a | b - XOR
a ^ b, - Left Shift
a << b - Right Shift
a >> b - One's Complement or NOT
~a
XOR is one of the most useful operations in cryptography. It takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different and 0 if they are same (hence the name Exclusive OR).
Example: 73 ⊕ 87 = (1001001)2 ⊕ (1010111)2= (0011110)2 = 30
XOR is both commutative and associative.
EXERCISE: Given an array find out the only element that occurs exactly once if every element other than the unique element occurs twice.
ANSWER : Just XOR all the elements of the array!For example, images can be XORed using gmic or PIL.
Text Guides:
- https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-and-the-one-time-pad
- https://betterexplained.com/articles/swap-two-variables-using-xor/
It is a method of encrypting plain text. The two requirements for the One-Time pad are:
- The key should be randomly generated as long as the length of the message.
- The key is to be used to encrypt and decrypt a single message and then it is discarded. So to encrypt every new message requires a new key of the same length.
Text Guides:
Unlike the (mostly) continuous math/analysis you must've studied during your JEE preparations / courses here at IIT Bombay, cryptography uses a lot of discrete math. For this week's content, you must be familiar with some number theory (modular theory) to understand RSA.
You can refer to the following link for a "cheat-sheet" of sorts: https://drive.google.com/file/d/1X_eIBpjRonnC216WJ2GfY6yl87u7VqVQ/view?usp=sharing
Text Guides:
Ah, the star scheme of this week. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who described the algorithm in 1977 (it's licensing has an interesting history, view https://www.computerworld.com/article/2588444/rsa-encryption-patent-released.html). RSA is a public-key cryptosystem that is used for secure data transmission. It is also one of the oldest.
Due to the incredible popularity of RSA, you can find hundreds of resources to study it online! However, so as to not get overwhelmed, you can refer to the following link for a short summary on RSA : https://drive.google.com/file/d/1-b-v0p2JQWum2Huk2Hp-UADEZ3D9MNOB/view?usp=sharing
One of the flaws that you might feel is present in RSA is that given n, we would just "factor" it to get p (hence q)! The truth is,
however factoring algorithms are SLOW. Given no specific property of n, the asymptotically fastest algorithm is Shor's algorithm which is a quantum
algorithm. However, if n satisfies certain special properties (which varies with factoring algorithm), it can be factored very fast.
So if you're reluctant, your best bet is to just spam all the factoring algorithms and hope one of them works!
To get a good summary, check out https://stackoverflow.com/questions/2267146/what-is-the-fastest-integer-factorization-algorithm
You will find many different attacks on RSA which also exploit e or ciphertext given certain cases.
To get a good list of attacks, check out https://github.com/RsaCtfTool/RsaCtfTool
However, in actual practice, the key sizes are 2048 to 4096 bits, refer https://crypto.stackexchange.com/questions/27575/why-isnt-a-table-used-to-solve-the-large-number-factoring-problem .
For example, you can view the public key of the website you're browsing in its certificate.
Text Guides:
Video Guides:
- https://youtu.be/JD72Ry60eP4 (there are many videos on RSA and other schemes on computerphile)
- https://cryptohack.org/challenges/
- https://cryptopals.com/
- https://play.picoctf.org/
- https://overthewire.org/wargames/krypton/
- https://ctflearn.com/
We have another 2 challenges lined up for you this time:
All in all, you would need to solve atleast 2 challenges throughtout the module but we encourage that you solve all of these, for things are more fun that way 😊.
Make sure you go through the respective README.md files before jumping into the challenge. Have fun! 😁
Discussions among mentees are encouraged and we request you to use our Discord Server for the same.
Created with ❤️ by CSec