Cryptographic Primitives PDF

University of BATNA 2 Department of Computer Science Chapter 2 Cryptographic Primitives Master 1 Distributed Information Systems Engineering and Security - A.Dekhinet  Cryptography  Cryptography is based on the u...

University of BATNA 2 Department of Computer Science Chapter 2 Cryptographic Primitives Master 1 Distributed Information Systems Engineering and Security - A.Dekhinet  Cryptography  Cryptography is based on the use of the mathematical principles in storing and transmitting data in a particular form so that only those whom it is intended can read and process it.  The main purpose of the cryptography, as science, is to preserve : Confidentiality : Information is kept secret from all but authorized parties. Integrity : Messages have not been modified or altered in transit. Authentication : The sender of a message is authentic. An alternative term is data origin authentication. Non-repudiation : The sender cannot deny later that they sent the message. This means that an entity cannot refuse the ownership of a previous commitment or an action.  Encryption function  The general principle of cryptography is based on the use of mathematical functions and algorithms to encrypt data.  An encryption function or algorithm, is a means of transforming plaintext into ciphertext under the control of a secret key, this process is called encryption or encipherment (‫)تشفير‬. c = Ek(m) m is the plaintext, E is the cipher function, k is the secret key, c is the ciphertext. The decryption or decipherment is the reverse process : m = Dk(c) Note that E and D are public, the secrecy of m given c depends totally on the secrecy of k. Types of cryptosystems  Three cryptosystems can be distinguished : Symmetric cryptography, Asymmetric cryptography, Hashing Symmetric cryptosystem (Secret key cryptosystem) : The communicating party use the same key (Shared key) for encryption and decryption. Asymmetric cryptosystem (Public key cryptosystem) : The communicating party use two different types of key, one is publicly available and used for encryption while the other is private and used for decryption. Cryptographic Hashing : Function used to transform large random size data to small fixed size data. The hash functions does not need any key (0-key).  Symmetric cryptosystem : One-Key  Symmetric cryptography is the oldest form of cryptosystem.  Some cyptosystem : Shift cipher, Caeser, Affine, Vigenere, Hill, AES, DES, IDEA, Blowfish, RC4, RC5, RC6, …  Example : In shift cipher Ek = (m+k) mod 26 and Dk = (c-k) mod 26  Asymmetric cryptosystem : Two-Key Based an idea proposed by Diffie, Hellman and Merkle : It is not necessary that the encryption key is secret.  Asymmetric cryptography uses a pair of keys: a public key and a private key that are mathematically related to each other.  The public key is made public without reducing the security of the process, but the private key is kept safe and private. Asymmetric cryptosystem : Two-Key In general, asymmetric cryptosystem scheme consists of three algorithms : 1. Key generation(KG): A public and private key pair (pk, sk) is generated, The public key pk is published to the public, while the private key sk is known to its owner only. 2. Encryption(E): Given a plaintext m and a public key pk, a ciphertext c is produced, denoted as c = E(m, pk). 3. Decryption algorithm (D): Given a ciphertext c = E(m, pk) and the private key sk, the plaintext m is recovered, denoted as m = D(c, sk)  Asymmetric cryptosystem : Two-Key  Families of asymmetric cryptograhy : Integer-Factorization Schemes : Several public-key schemes are based on the fact that it is difficult to factor large integers. The most prominent representative of this algorithm family is RSA (Rivest–Shamir–Adleman). Discrete Logarithm Schemes : There are several algorithms which are based on what is known as the discrete logarithm (DL) problem in finite fields. The most prominent examples include the Diffie–Hellman key exchange, Elgamal encryption or the Digital Signature Algorithm (DSA). Elliptic Curve (EC) Schemes : A generalization of the discrete logarithm algorithm is elliptic curve public-key schemes. The most popular examples include Elliptic Curve Diffie–Hellman key exchange (ECDH) and the Elliptic Curve Digital Signature Algorithm (ECDSA). RSA is the most widely used asymmetric cryptographic scheme. Therefore, Blockchain is principally based on elliptic curve scheme.  Asymmetric cryptosystem : RSA  Generally used for encryption of small pieces of data, especially for key transport, digital signatures, digital certificates, …  The keys generation is done by following steps : public key : kpub = (n,e) and private key : kpr = (n,d) Choose two large primes p and q Compute n = p · q Compute (n) = (p−1)(q−1) Select the public exponent e ∈ {1,2,... ,(n)−1} such that gcd(e,(n))=1 Compute the private key d such that d·e ≡ 1 mod (n) or d ≡ e -1mod (n) Encryption function : c = me mod n Decryption function : m = cd mod n  Asymmetric cryptosystem : RSA Example with small prime numbers (in practice very large prime numbers are needed) We choose two prime numbers p = 3, q = 11 ; Their product n = 3 × 11 = 33 is the encryption module ; φ(n) = (3 – 1) × (11 – 1) = 2 × 10 = 20 ; We choose e= 3 (prime with 20) as encryption exponent; The decryption exponent is d = 7, the inverse of 3 modulo 20 (in effect e. d = 3 × 7 ≡ 1 mod 20) ; Alice's public key is (n, e) = (33, 3), and her private key is (n, d) = (33, 7) Bob sends a message to Alice : Encryption of m = 4 by Bob with Alice's public key: 43 ≡ 31 mod 33, the cipher is c = 31 which Bob transmits to Alice; Decryption of c = 31 by Alice with her private key: 317 ≡ 4 mod 33, Alice finds the initial message m = 4.  Asymmetric cryptosystem : Diffie–Hellman key exchange  The Diffie–Hellman key exchange DHKE (Symetric key agreement) scheme enables two parties to derive a common secret key (Symmetric key ) by communicating over an insecure channel.  It’s widely used in cryptographic protocols, such SSL/TLS, …  The basic idea behind the DHKE is the exponentiation in Zp, p prime, is commutative (ga)b mod p = (gb)a mod p  DHKE is based on the discrete logarithm problem in finite fields Knowing the value of gi mod p , g and p it’s very difficult to find i  DHKE steps : Setup and main protocols Setup Alice and Bob choos two numbers p and g : Domain parameters, Public p is a large prime number on the order of 300 decimal digits (1024 bits) g is a primitive root of p named generator Asymmetric cryptosystem : Diffie–Hellman key exchange Main Alice chooses a large random number a (kpr,A) such that 1