Network Security and Cryptography RSA variant. Let us consider the following variant of the RSA public key encryption scheme, named RSA-M1 = (KG1, Enc1, Dec1). The corresponding key generation and encryption algorithms are detailed next: • Key generation KG¡(A) Generate two distinct odd primes p and q of same bit-size d - Compute N = p•q and o = (p – 1)(q – 1) - Select a random integer 1 < e <¢ such that gcd(e, ø) = 1 - Compute the unique integer d such that 1 < d < ¢ and e.d = 1 mod ¢ The public key is PK = (N, e). The private key is SK (N, e, d) %3D Encryption Enc1(PK, m) of a message m e ZN proceeds as fol- lows: Generate a random integer r in ZN - Compute îm =m•r mod N - Compute ci = mº mod N Compute c2 =r=e mod N %3D - Output C = (c1, c2) %3D (a) Give the corresponding decryption algorithm Dec1 (SK,C). Prove your decryption algorithm is correct, i.e. given a legitimate key pair (PK, SK) + KG|(A) it holds that Dec1 (SK, Enc1(PK,m)) m for any admissible plaintext m. (b) Is the public key encryption scheme RSA-M1 one-way? Justify your answer.

Network Security and Cryptography RSA variant. Let us consider the following variant of the RSA public key encryption scheme, named RSA-M1 = (KG1, Enc1, Dec1). The corresponding key generation and encryption algorithms are detailed next: • Key generation KG¡(A) Generate two distinct odd primes p and q of same bit-size d - Compute N = p•q and o = (p – 1)(q – 1) - Select a random integer 1 < e <¢ such that gcd(e, ø) = 1 - Compute the unique integer d such that 1 < d < ¢ and e.d = 1 mod ¢ The public key is PK = (N, e). The private key is SK (N, e, d) %3D Encryption Enc1(PK, m) of a message m e ZN proceeds as fol- lows: Generate a random integer r in ZN - Compute îm =m•r mod N - Compute ci = mº mod N Compute c2 =r=e mod N %3D - Output C = (c1, c2) %3D (a) Give the corresponding decryption algorithm Dec1 (SK,C). Prove your decryption algorithm is correct, i.e. given a legitimate key pair (PK, SK) + KG|(A) it holds that Dec1 (SK, Enc1(PK,m)) m for any admissible plaintext m. (b) Is the public key encryption scheme RSA-M1 one-way? Justify your answer.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

The parity function is a very simple hash function producing a one-bit digest, which is 0 if the number of bits in the message is even and 1 if it is odd. Consider a communication system that uses 7 bits out of every byte to transmit data, and reserves the 8th bit (the one on the right) to transmit the parity of the other seven bits, for purposes of error checking. Below is the binary representation of some bytes that were transmitted using this system. For each one, tell whether there is a reason to suspect an error in transmission, giving the reason for your answer. 10110011 11101111 10101100 00110011
2. Let (M, C, e, d, K) denote the simple substitution cryptosystem with Σ = {0, 1, 2, 3, 4), M = C = * = {0, 1, 2, 3, 4}*, and -(01234). ők = (a) Compute C= e(240014, k). (b) Compute M = d(4130, k).
(b) Suppose we have public key encryption system with E the encryption function and Dr the decryption function, where Er is publicly known for a key k and Dx is secret. Suppose further that the composition of the operations E and Dµ is com- mutative: Er o Dr = Dx o Ex. Propose a simple way to implement authenticating messages using components of this encryption system. Answer: to send a signed message x we compute and send:
An old encryption system uses 20-bit keys. A cryptanalyst, who wants to brute-force attack theencryption system, is working on a computer system with a performance rate N keys per second. How many possible keys will be available in the above encryption system? What will be the maximum number of keys per second (N) that the computer system isworking with, if the amount of time needed to brute-force all the possible keys was 512 milliseconds? Show you detailed calculations.
RSA variant. Let us consider the following variant of the RSA publickey encryption scheme, named RSA-M1 = (KG1, Enc1, Dec1). Thecorresponding key generation and encryption algorithms are detailednext:• Key generation KG1(λ)– Generate two distinct odd primes p and q of same bit-size λ– Compute N = p · q and ϕ = (p − 1)(q − 1)– Select a random integer 1 < e < ϕ such that gcd(e, ϕ) = 1– Compute the unique integer d such that 1 < d < ϕ ande · d = 1mod ϕ– The public key is PK = (N, e). The private key is SK =(N, e, d)• Encryption Enc1(PK,m) of a message m ∈ Z⋆N proceeds as follows:– Generate a random integer r in Z⋆N– Compute bm = m · r modN– Compute c1 = bme modN– Compute c2 = r−e modN– Output C = (c1, c2) (a) Give the corresponding decryption algorithm Dec1(SK,C). Proveyour decryption algorithm is correct, i.e. given a legitimate keypair (PK, SK) ← KG1(λ) it holds that Dec1(SK, Enc1(PK,m)) =m for any admissible plaintext m.(b) Is the public key encryption scheme RSA-M1…
Exercise 2 (MAC schemes derived from block ciphers( Let E denote the family of encryption functions for a block cipher where plaintext blocks, ciphertext blocks, and keys are each n = 80 bits in length. Let H {0, 1} {0, 1}" be a hash function. Assume that plaintext messages m all have bit-lengths that are multiples of n; we write m = (my, m₂,...,m), i.e. m is composed of t blocks m, of n bits each. Consider the following MAC schemes, each using an n-bit secret key k. 1. MAC (m) = ₁, where co = 0, and c, =c-1m, Ex(m) for 1 ≤ i ≤t. 2. MAC (m) Ek(H(m)). Are any of these MAC schemes secure? Justify your answer and clearly state any assumptions you make.
Msg3. B→A : B, N1, Ks, Message2, h(B, N1, Message2) Whereas: h(m) represents the digest of the message (m). {m}{K} represents the encryption of message (m) using the key (K) PK is public key N1 is a random number. 1. What are the main problems in Msg3?
Exercise 2 (MAC schemes derived from block ciphers ( Let E denote the family of encryption functions for a block cipher where plaintext blocks, ciphertext blocks, and keys are each n = 80 bits in length. Let H: {0,1} {0, 1}" be a hash function. Assume that plaintext messages m all have bit-lengths that are multiples of n; we write m = (m₁, m₂,...,m), i.e. m is composed of t blocks m, of n bits each. Consider the following MAC schemes, each using an n-bit secret key k. 1. MAC (m) = ct, where co= 0, and c = c-1m, E(m) for 1 ≤ i ≤t. 2. MACk (m) Ek(H(m)). = Are any of these MAC schemes secure? Justify your answer and clearly state any assumptions you make.
2 Consider a very simple symmetric block encryption algorithm in which 32-bits blocks of plaintext are encrypted using a 64-bit key. Encryption is defined as C = (PK₁) K₁ where C = ciphertext, K = secret key, Ko = leftmost 64 bits of K, K₁= rightmost 64 bits of K, = bitwise exclusive OR, and is addition mod 264. a. Show the decryption equation. That is, show the equation for P as a function of C, Ko, and K₁. b. Suppose and adversary has access to two sets of plaintexts and their correspond- ing ciphertexts and wishes to determine K. We have the two equations: C = (PK) K₁; C = (PK) K₁ First, derive an equation in one unknown (e.g., Ko). Is it possible to proceed fur- ther to solve for Ko?
Suppose that Alice and Bob communicate using ElGamal cipher and f (p. 9. Z) is common public values. Bob generates his private key d ER Z and then computes the corresponding and public public key y=g" (mod p). To save time, Bob uses the same number r each time he encrypts a plaintext message m (ie., r is a fixed nonce of Bob, and it is not randomly generated each time encryption is performed). Assume that Alice compute the ciphertext for the message m as (cc) = (g mod p, mxy mod p). and for the message m as (1,2)=(g" mod p, xy' mod p). Show how an adversary who possesses a plaintext-ciphertext pair (m. (c.ca)) can decrypt (1, 2) without knowing the private key d of Bob.
Exercise 13 Name: 11.5 (Multiplicative ElGamal). Let G be a cyclic group of prime order q generated by g € G. Consider a simple variant of the ElGamal encryption system EMEG = (G. E, D) that is defined over (G. G²). The key generation algorithm G is the same as in EEG, but encryption and decryption work as follows: ⚫ for a given public key pku G and message mЄ G: E(pk, m) := eum, output (v, e) ⚫ for a given secret key sk= a € Zq and a ciphertext (v,e) € G²: D(sk, (v, e)) e/v Show that EMEG has the following property: given a public key pk, and two ciphertexts C1E(pk, m) and c2 E(pk, m2), it is possible to create a new ciphertext e which is an encryption of m₁ m2. This property is called a multiplicative homomorphism.
EXAMPLE: Kocher’s timing attacks on cryptosystems illustrate this [1084]. Kocher notes that the instructions executed by implementations of cryptosystems depend on the setting of bits in the key. For example, the algorithm in Figure 9–7 implements a fast modular exponentiation function. If a bit is 1, two multiplications occur; otherwise, one multiplication occurs. The extra multiplication takes extra time. Kocher determines bits of the confidential exponent by measuring computation time x:= 1; atmp := a; for 1 := 0 to k-1 do begin If Zi = 1 then x := (x * atmp) mod n; atmp := )atmp * atmp) mod n; end; result := x; Figure 9–7 A fast modular exponentiation routine. This routine computes x = az mod n. The bits of z are zk–1... z0. Kocher’s attack derives information about the computation from the characteristic of time. As a cryptographic key is confidential, this is a side channel attack. This is an example of a passive side channel attack, because results are derived only from…