Number Theory (Part E)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
February 16, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 1 / 15
1 Classical Cryptography
2 Public Keys and RSA
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 2 / 15
Classical Cryptography
Caesar’s Cipher
To express Caesar’s encryption process mathematically, first replace each letter by an element of Z26, that is, an integer from 0 to 25 equal to one position less than its position in the alphabet.
Encryption: f (p) = (p + k) mod 26 Decryption: f −1(p) = (p − k) mod 26
• k is called the key.
• This type of cipher is called a shift cipher.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 3 / 15
Classical Cryptography (cont.)
Example: Caesar’s Cipher
Encrypt the plaintext message “STOP” using Caesar’s cipher with k = 11.
Decrypt the ciphertext to verify its correctness.
Numerical equivalent: 18 19 14 15 p+11: 29 30 25 26
(p + 11) mod 26: 3 4 25 0 Encrypted message: DEZA
Numerical equivalent of the encrypted message: 3 4 25 0 p−11: -8 -7 14 -11
(p−11) mod 26: 18 19 14 15
Decrypted message: STOP
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 4 / 15
Classical Cryptography (cont.)
Cryptoanalysis
The process of recovering plaintext from ciphertext without knowledge of both the encryption method and the key is known as cryptoanalysis or breaking code.
Block Ciphers
Ciphers that replace blocks of letters with other blocks of letters are called block ciphers.
Shift ciphers such as the Caesar’s cipher are monoalphabetic. Block ciphers are more secure than monoalphabetic ones.
Transposition Ciphers
The transposition cipher is a simple block cipher that uses a permutation
of blocks of letters to encrypt a message.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 5 / 15
Classical Cryptography (cont.)
Cryptosystems
A cryptosystem is a five-tuple (P,C,K,E,D), where P is the set of plaintext strings, C is the set of ciphertext strings, K is the keyspace (the set of all possible keys), E is the set of encryption functions, and D is the set of decryption functions.
Ek is the encryption function in E corresponding to the key k.
Dk is the decryption function in D that decrypts the ciphertexts obtained using Ek.
Dk (Ek (p)) = p, for all plaintext strings p.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 6 / 15
Public Key Cryptosystems
Private Key Cryptosystems
Each pair of communicating parties requires a unique secret key. The same
key is used to encrypt and decrypt a message. Such a system is also known
as a symmetric cryptosystem. For N people, it requires N secret keys. 2
Public Key Cryptosystems
To avoid the need for a huge number of secret keys, the concept of public key cryptosystems was introduced in 1970s. In such a system, everyone requires a pair of keys. Each pair consists of a public key and a private key. Thus, for N people, it only requires 2N keys. The public key of a communicating party is available to others while the private key is only known to its owner.
Alice needs to encrypt a message using Bob‘s public key. Bob needs to use his private key to decrypt the message.
In general, public key systems require a heavy processing time.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 7 / 15
The RSA Cryptosystem
The RSA is a public key cryptosystem named after its inventors’ surnames. It was introduced in 1976 by three researchers at MIT.
The public encryption key is (n, e), where n = pq (the modulus) is the product of two large (say 300 digits) primes p and q, and an exponent e that is relatively prime to (p − 1)(q − 1).
The decryption key d , an inverse of e modulo (p − 1)(q − 1). Thus, the pair of keys is given by
de ≡ 1 (mod (p − 1)(q − 1)).
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 8 / 15
RSA Encryption
To encrypt a plaintext message using RSA using a key (n,e) the following steps are required:
• Translate the plaintext message M into a sequence of two digit integers representing the letters. Use 00 for A, 01 for B, etc.
• Concatenate the two digit integers into a string of digits.
• Divide the string into equally sized blocks of 2N digits where 2N is the
largest even number 2525…25 with 2N digits that does not exceed n.
• The plaintext message M is now a sequence of integers m1, m2, , mk. • Each block (an integer) is encrypted using the function c = me mod n.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 9 / 15
RSA Decryption
To decrypt an RSA ciphertext message, the decryption key d, an inverse of e modulo (p − 1)(q − 1) is used.
• The inverse exists since gcd(e, (p − 1)(q − 1)) = 1. It follows de ≡ 1 (mod (p − 1)(q − 1)).
• There is an integer k such that de = 1 + k(p − 1)(q − 1). It follows that cd ≡ (me)d = mde = m1+k(p−1)(q−1) (mod n).
• cd ≡ m1+k(p−1)(q−1) (mod n).
• Assuming gcd(m, p) = gcd(m, q) = 1 and applying Fermat’s little theorem
cd ≡m·(mp−1)k(q−1) ≡m·1=m(modp)and
cd ≡m·(mq−1)k(p−1) ≡m·1=m(modq).
• Finally, cd ≡ m (mod n).
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 10 / 15
RSA Example
Encrypt the message STOP using the RSA cryptosystem with key (2537, 13). Note that 2537 = 43·59, p = 43 and q = 59 are primes.
The numerical equivalent of STOP is 18 19 14 15.
As 2525 < 2537 < 252525, these numbers are broken into blocks of four digits: 1819 and 1415.
The first block becomes 181913 mod 2537 = 2081 and the second block becomes 141513 mod 2537 = 2182.
The decryption key is 937. If we decrypt the blocks, we get 2081937 mod 2537 = 1819 and 2182937 mod 2537 = 1415.
Note: The decryption key d = (2436k + 1)/13 for an integer k. In this example k = 5.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 11 / 15
Cryptographic Protocols
Cryptographic protocols are used to achieve security goals between communicating parties. For example, secret keys are exchanged over an insecure communication channel.
Alice and Bob want to share a common key. The protocol follows these
steps, where the computations are done in Zp.
– Both parties agree to use a prime p and a primitive root a of p. – Alice chooses a secret integer k1 and sends ak1 mod p to Bob. – Bob chooses a secret integer k2 and sends ak2 mod p to Alice. – Alice computes (ak2 )k1 mod p.
– Bob computes (ak1 )k2 mod p.
– As a result, a shared key, k = (ak2)k1 mod p = (ak1)k2 mod p is exchanged.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 12 / 15
Cryptographic Protocols (cont.)
• Alice does not know the value of k2 • Bob does not know the value of k1
• To break the security:
– It is necessary to find k1 from ak1 mod p – It is necessary to find k2 from ak2 mod p
• It is computationally infeasible for an adversary to obtain k1 and k2 when p and a are sufficiently large.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 13 / 15
Cryptographic Protocols (cont.)
Digital Signatures
Digital signatures are used to verify that a message is actually sent by the purported sender. The verification is done at the receiver side. It is associated with certain cryptographic protocols.
• Suppose Alice wants to broadcast a message M. She can use her private key to generate a digital signature. The recipients then use Alice’s public key to verify the message. It can be expressed in a simplified manner as follows (kpriv and kpub are private and public key pair)
Encryption function to generate a signature Ekpriv (M)
Decryption function to verify the signature Dkpub (Ekpriv (M)) = M′
If M′ = M, the sender is verified.
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 14 / 15
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 4e MdH W22 February 16, 2022 15 / 15
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com