Chapter 4-1: Asymmetric Cryptography, RSA - King Khalid University 2024 PDF

Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Course Cryptography (Classic & Modern) Dr. Ahmed AlMokhtar Ben Hmida Co...

Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Course Cryptography (Classic & Modern) Dr. Ahmed AlMokhtar Ben Hmida College of Computer Science, King Khaled University 'KKU', KSA okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA No List of Topics Contact Hours 1. Review of number theory, Probability and Statistics Ch01 Maths 4 2. Security functions of cryptography Ch1 8 Intro & Ch2 Classical 3. Symmetric cryptography Ch3 8 4. Public key cryptography Ch4 8 5. Key generation, Management, Exchange and distribution 8 Ch5 6. Digital certificate Ch6 2 7. Hash functions Ch6 4 8. Digital signature Ch7 4 9. Collision resistance Ch7 2 10. Common Cryptographic Protocols and standards Ch8 4 11. Types of cryptographic attacks Ch9 4 okhtar BEN 12.HMIDA, Dr. & Full Professor, Cryptographic Head of ATMS Implementation Processing , Lab, Expert in Signal Ch10 failures CS4College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Introduction to Cryptography Definition Main objectives Characteristics of a cryptosystem Course Map Symmetric cryotpgraphy Including Definition/property/principle Study of the DES algorithm all Topics Asymmetric cryotpgraphy of the ‘CS’ Definition/property/principle Study of the RSA algorithm Digital signature Hashing okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 4-1 : Asymmetric Cryptography, Public Key, RSA… Asymmetric Cryptography: History & Principle  RSA Algorithm (Formalism)  RSA Algorithm EXAMPLES okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 4-1 : Asymmetric Cryptography, Public Key, RSA… Asymmetric Cryptography: History & Principle  RSA Algorithm (Formalism)  RSA Algorithm EXAMPLES okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA En gori Al cr t h yp m tio s n okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Cryptography, Public Key Encryption and Signatures Pbs with Symmetric Cryptography  Asymmetric Cryptography, Public key technique, was originally invented to solve the key distribution problem and Any exposure to the secret to provide authenticity. key compromises secrecy of ciphertext  Many advantages over symmetric systems, the main one is that they do not require two communicating parties to know A key needs to be delivered each other before encrypted communication can take place. to the recipient of the coded message for it to be  In addition, the use of digital signatures allows users to sign deciphered digital data such as electronic orders or money transfers. Potential for eavesdropping attack during transmission of key  Hence, public key technology is one of the key enabling technologies for e-commerce and a digital society. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Public Key Encryption Transmitting confidential messages via the internet is possible using public key encryption. A public key and a private key are the two keys that the user of this technique applies. While the public key is shared, the private key is kept secret. For encrypted messages intended to be sent to another client, the client's public key is used for encryption. If the communication is encrypted and can only be decrypted with the receiver's private key, only that person can access it. This option is important for secure communication when sending sensitive data such as passwords, credit card numbers, or private contacts. Protecting our data from attackers and hackers helps. It is also called as Asymmetric Key Cryptography. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA History of Public Key Encryption: Whitfield Diffie, Ralph Merkle, Martin Hellman Paper titled "New Directions in Cryptography" in 1976. First known functional distributed cryptography protocol and presented the concept of public key cryptography in this study. Since then, two mathematically related keys have been used for the Public Key Encryption technique, which is used in finance, e-business, and e-commerce to protect data. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Properties of Public key Encryption  For encryption and decryption, separate keys are used. This characteristic differentiates this system from symmetric encryption schemes.  Each recipient has a distinct decryption key, also called his private key.  The recipient must make his public key-an encryption key-public.  Under order to prevent someone else from acting as the recipient under this method, some assurance of the legitimacy of a public key is required.  Typically, this kind of cryptosystem involves a reliable third party verifying that a certain public key is unique to a particular individual or organisation.  Because of the complexity of the encryption technique, an attacker cannot decrypt the plaintext from the ciphertext and the encryption (public) key.  Secret key cannot be determined from the public key, even with the mathematical link between the public and private keys. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Public Key Cryptography Algorithms  RSA (Rivest-Shamir-Adleman)  ElGamal  DSA (Digital Signature Algorithm)  ECC (Elliptic Curve Cryptography)  Diffie-Hellman Key Exchange These algorithms are used in many encryption protocols and systems to create secure communication and data transmission over the web. RSA was evolved in 1977 via MIT researchers: Ron Rivest, Adi Shamir and Leonard Adleman, whose name bears the set of rules’s call. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Applications It is very helpful for situations where you need to communicate information securely over a network, particularly a public network, and a standard key will not work.  Web Traffic Security − If you see a small lock icon in your web browser's address bar or a web address that begins with "https://" rather than "http://", it shows the website is using an SSL certificate. This SSL certificate is very important since it protects your personal information when you make online purchases. It also helps to ensure that the page you are on is truly who they claim to be, which helps prevent tricks like phishing scams.  Email Encryption − Most email services use TLS security to secure emails when we send or receive them. This means that, while your emails are not hidden in your inbox, they are protected from malicious users trying to read them.  Virtual Private Networks (VPNs) − VPNs are very useful for firms with workers that work from home or around the world. They keep everything safe, confidential, and simple to use. To keep the VPN secure, they use asymmetric encryption, which is similar to TLS or SSL. It helps to make sure that users are who they say they are and protects data as it travels between users and the company's primary system. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Cryptography, Notation & Principle Key distribution problems are solved by asymmetric cryptography, the concept of which was invented by Whitfield Diffie and Martin Hellman in 1975. Asymmetric cryptography represents a revolution in the history of cryptography. Notation : also called Public & Private Key / key pair cryptography Principle : it is based on an asymmetric scheme that uses a pair of keys for encryption: a public key, which encrypts the data, and a corresponding private key, also called a secret key, which will be used for decryption. two keys : okhtar BEN HMIDA,key: Public Dr. & Known Full Professor, Head of ATMS by everyone, andLab, canExpert in Signal be used encrypt ,messages. toProcessing CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Cryptography, Public Key Encryption and Signatures  Symmetric key Cryptography: each communicating party needed to have a copy of the same secret key. This led to a very difficult key management problem.  Public key cryptography: two keys, one Key Public and one Key Private.  Public key can be published in a directory along with the user ’s name.  Anyone who wishes to send Message to the holder of the associated Private key will take Public key, encrypt a message under it, and send it to the owner of the corresponding Private key.  The idea is that only the holder of the Private key will be able to decrypt the message.  More clearly, we have the transforms :  Message + Alice’s public key = Ciphertext,  Ciphertext + Alice’s private key = Message.  Hence anyone with Alice’s public key can send Alice a secret message. But only Alice can decrypt the message, since only Alice has the corresponding private key. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Cryptography, Public Key Encryption and Signatures  Public key cryptography : The two keys are linked in a mathematical way, such that knowing the Public key tells you nothing about the Private key.  But knowing the Private key allows you to unlock information encrypted with the Public key.  This may seem strange, and will require some thought and patience to understand.  The concept was so strange it was not until 1976 that anyone thought of it.  The idea was first presented in the seminal paper of Diffie and Hellman entitled New Directions in Cryptography.  Although Diffie and Hellman invented the concept of Public key cryptography; it was not until a year or so later that the first (and most successful) system, namely RSA, was invented. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Cryptography, BASICS ; Public Key, Private Key… Uses a pair of keys for encryption Public key for encryption Private key for decryption Messages encoded using public key can only be decoded by the private key Secret transmission of key for decryption is not required Every entity can generate a key pair and release its public key Plain Text Cipher Cipher Text Cipher Plain Text Public Key Private Key okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Cryptography, Dk' ( Ek (M) ) = M ; Public Key, It is assumed Private Key… that Alice wants to send a secret message to Bob Plaintex Cipherte Plainte t xt xt Public Key Private Key Alice Bob Ek (Encryption function) and Dk' (Decryption function) can be found which depend respectively on the keys k and K'. Dk' ( Ek (M) ) = M It is impossible (very difficult!!!) to find Dk' without knowledge of Ek Impossible to find Dk' knowing Ek and messages encrypted by Ek Ek and Dk' are easy to calculate. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 4-1 : Asymmetric Cryptography, Public Key, RSA… Asymmetric Cryptography: History & Principle  RSA Algorithm (Formalism)  RSA Algorithm EXAMPLES okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA En gori Al cr t h yp m tio s n okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Cryptography: Two most popular algorithms are RSA & El Gamal RSA Developed by Ron Rivest, Adi Shamir, Len Adelman Both public and private key are interchangable Variable Key Size (256, 512, 1024, or 2048 bits) Most popular public key algorithm El Gamal Developed by Taher El Gamal Variable key size (512 or 1024 bits) Less common than RSA, used in protocols like PGP okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA RSA Algorithm Developed by Rivest, Shamir & Adleman at MIT in 1977, published in 1978… The best known and most widely used asymmetric encryption algorithm. Uses very large integers key size 1024 bits and more Security relies on the cost of factoring large integers. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA RSA … Working RSA RSA algorithm is based on three main steps, namely : 1- Key generation, 2- Encryption message, and 3- Decryption message. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA 1- RSA Key GENERATION Key creation step is Alice's responsibility. It does not occur with each encryption because the keys can be reused, the first difficulty, which encryption does not solve, is that Bob is sure that the Public key he holds is that of Alice. Key renewal only occurs if the Private key is compromised, or as a precaution after a certain period of time. 1. Choose p and q, two distinct prime numbers; 2. Calculate their product n = p.q, called encryption modulus; 3. Calculate φ(n) = (p ‐ 1)(q ‐1); 4. Choose a prime number e with φ(n); gcd[φ(n),e]=1; strictly e < φ(n), encryption exponent; 5. Calculate the natural number d, inverse of e modulo φ(n), and strictly < φ(n), called the HMIDA, okhtar BEN decryption Dr. &exponent; d Head Full Professor, can be computed of ATMS efficiently Lab, Expert by the extended in Signal Processing , Euclidat King Kh CS College  Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA 2- & 3- RSA Algorithm 2- Encryption Message If M is a natural integer strictly less than n (M