**Knapsack Cryptosystem Example**---### Problem DescriptionGiven:- Superincreasing sequence: \( \mathbf{r} = (1, 3, 7, 15, 30, 61, 124) \).- Constants: \( A = 5 \) and \( B = 253 \).#### (a) Compute the SequenceLet \( M = (M_1, M_2, M_3, M_4, M_5, M_6, M_7) \), where:\[ M_i \equiv A r_i \ (\text{mod} \ B) \ \text{for} \ i = 1, 2, \ldots, 7. \]#### (b) Choose the Binary PlaintextLet the plaintext be \( x = (1, 0, 1, 1, 0, 1, 1) \).Compute the ciphertext:\[ S = x \cdot M. \]#### (c) Compute Intermediate ValueCompute the intermediate value:\[ S' = A^{-1} S \ (\text{mod} \ B). \]#### (d) Solve the Subset-Sum ProblemSolve the subset-sum problem \( S' \) using the superincreasing sequence \( \mathbf{r} \).---### Explanation of Parameters and Steps1. **Superincreasing Sequence \( \mathbf{r} \)**: This sequence is a specific type of sequence where each element is greater than the sum of all previous elements. In this case, \( \mathbf{r} = (1, 3, 7, 15, 30, 61, 124) \).2. **Computing \( M \)**: \[ M_i \equiv A r_i \ (\text{mod} \ B) \] - Multiply each element of \( \mathbf{r} \) by \( A \) and then take modulo \( B \) to find each \( M_i \).3. **Binary Plaintext \( x \)**: A binary vector representing the plaintext message. Each element of the vector is a bit (0 or 1).4. **Ciphertext Calculation**: \[ S = x \cdot M \] - Compute the dot product of the plaintext vector \( x \) with the computed sequence \( M

We have to solve knapsack cryptosystem of all the part is given .

(9) (Knapsack cryptosystem) Let r = (1, 3, 7, 15, 30, 61, 124). Let A = 5 and B = 253. (a) Compute the sequence where M = (M₁, M2, M3, M4, M5, M6, M7) M₁ Arį (mod B) (b) Choose the binary plaintext for i=1,2,...,7. x = (1, 0, 1, 1, 0, 1, 1) and compute the ciphertext S = x. M. (c) Compute S'A¹S (mod B) (d) Solve the subset-sum problem S' using the superincreasing sequence r.

(9) (Knapsack cryptosystem) Let r = (1, 3, 7, 15, 30, 61, 124). Let A = 5 and B = 253. (a) Compute the sequence where M = (M₁, M2, M3, M4, M5, M6, M7) M₁ Arį (mod B) (b) Choose the binary plaintext for i=1,2,...,7. x = (1, 0, 1, 1, 0, 1, 1) and compute the ciphertext S = x. M. (c) Compute S'A¹S (mod B) (d) Solve the subset-sum problem S' using the superincreasing sequence r.

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

Related questions

Q: Question 5 a) Roger wants to send Simon a message asking him to transfer RM6,000 to his account.…

Q: Change to Clause form HW ((X)a)(XA) ^ ([((°X)P<[(Z°x)2](ZE))(IE)V(I°X)]=[(X)qv(X)])(XA)

A: clauses change given in next step:

Q: DONT USE AI, USE PENCIL AND PAPER WHILE SOLVING SHOW ANSWER AND RESULTS An RSA cipher has public key…

A: To decrypt an RSA ciphertext, you need the private key d. The private key is computed using the…

Q: 1

A: Answer 1:-

Q: (1 point) Note: The notation from this problem is from Understanding Cryptography by Paar and Pelzl.…

A: To classify the given polynomials, we need to determine if they are primitive, irreducible, or…

Q: hapter 2: Problem 5 Previous Problem Problem List Next Problem (1 point) Note: The notation from…

A: AnswerDetermining Tap Bits for an LFSRStep 1. Identify the Polynomial- The given polynomial is ::…

Q: Consider the following mode of block cipher operation: C₁ = Ex(C-1) @P for i>I Ex(IV) Pi C₁ H where…

A: The given formula for Encryption is as follows: Ci = EK(Ci - 1)⊕Pi for i > 1 If i = 1, then the…

Q: im not sure whats wrong

A: Determining the Tap Bits of a Linear Feedback Shift Register (LFSR)Problem SetupGiven:Plaintext:…

Q: 2.8. Alice and Bob agree to use the prime p = 1373 and the base g = 2 for communications using the…

A: According to the Bartleby guideline, we are supposed to answer only 3 sub part of a question at a…

Q: Why does PGP generate a signature before applying compression? How does PGP use the concept of…

A: PGP (Pretty Good Privacy) is a cryptographic protocol that helps ensure the secure transmission of…

Q: (Show your work.) Consider the Affine Cipher in English Alphabet with the key (a, b) - = (7, 22).…

A: Approach to solving the question:Please see attached photos for detailed solutions. Thank you.…

Q: Exercise 2 (MAC schemes derived from block ciphers( Let E denote the family of encryption functions…

A: we assume that it is not collision resistant, i.e. we can find a pair of messages x and y where xty…

Q: key (71, 7, 32) and private key k = 30: (56, 45) (56, 38) (56, 29) (56, 03) (56, 67) (56, 05) (56,…

A: Answer of two we use descryption formula to find plain text:…

Q: 2) Encode the letters 'A' to 'Z' as the numbers 10 to 35, respec- tively. Taking p = 47, q = 83, use…

A: To encode the message using the Rabin cryptosystem, we need to assign numerical values to the…

Q: 8- For Hamming Code of (7, 4), if the received code words are as the fallowing: C1-[1010111],…

A: To solve the given problem, we will use the Hamming Code (7, 4) scheme, which means the original…

Q: (c) Show that (m^n) ⇒ (mVn) = T

A: Statement is stating that the logical implication "m Λ n" implies "m V n" is always true…

Question

**Knapsack Cryptosystem Example**

---

### Problem Description

Given:
- Superincreasing sequence: \( \mathbf{r} = (1, 3, 7, 15, 30, 61, 124) \).
- Constants: \( A = 5 \) and \( B = 253 \).

#### (a) Compute the Sequence

Let \( M = (M_1, M_2, M_3, M_4, M_5, M_6, M_7) \), where:
\[ M_i \equiv A r_i \ (\text{mod} \ B) \ \text{for} \ i = 1, 2, \ldots, 7. \]

#### (b) Choose the Binary Plaintext

Let the plaintext be \( x = (1, 0, 1, 1, 0, 1, 1) \).

Compute the ciphertext:
\[ S = x \cdot M. \]

#### (c) Compute Intermediate Value

Compute the intermediate value:
\[ S' = A^{-1} S \ (\text{mod} \ B). \]

#### (d) Solve the Subset-Sum Problem

Solve the subset-sum problem \( S' \) using the superincreasing sequence \( \mathbf{r} \).

---

### Explanation of Parameters and Steps

1. **Superincreasing Sequence \( \mathbf{r} \)**: This sequence is a specific type of sequence where each element is greater than the sum of all previous elements. In this case, \( \mathbf{r} = (1, 3, 7, 15, 30, 61, 124) \).

2. **Computing \( M \)**:
\[ M_i \equiv A r_i \ (\text{mod} \ B) \]
- Multiply each element of \( \mathbf{r} \) by \( A \) and then take modulo \( B \) to find each \( M_i \).

3. **Binary Plaintext \( x \)**: A binary vector representing the plaintext message. Each element of the vector is a bit (0 or 1).

4. **Ciphertext Calculation**:
\[ S = x \cdot M \]
- Compute the dot product of the plaintext vector \( x \) with the computed sequence \( M

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

SEE SOLUTION Check out a sample Q&A here

Step 1: Given information:

VIEW

Step 2: Answers:

VIEW

Solution

VIEW

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

find a
Please see attached
Asymtotic Analysis : Prove the following claims
Cryptoghraphy question : a. Describe the RSA encryption and decryption algorithms b. Consider using RSA encryption with n = 209 = (11)x(19). What is wrong with using e = 5 as the encryption key? What is the smallest and the largest e that would work?
A.Given p=25, q=9, and e=7, generate the public key (n,e) and the private key (n,d) using the RSA Key generation algorithm. (Use Excel for computations) b. Given Bob's public key of (85, 7) and private key of (85, 55), show how Alice can encrypt m=3 to send to Bob. Show the ciphertext. c. Given Bob's public key of (85, 7) and private key of (85, 55), show how Bob can decrypt the ciphertext y=2 received from Alice. Show the plaintext. d. Using the fast exponentiation method, determine 530 mod 47. Show your work.
Aes algorithm for symmetric cryptography a) In AES Given the plaintext (000102030405060708090A0B0CEOF) and the key (01010101010101010101010101010101) Show the original contents of State, displayed as a 4x4 matrix
(1 point) Note: The notation from this problem is from Understanding Cryptography by Paar and Pelzl. We conduct a known-plaintext attack against an LFSR. Through trial and error we have determined that the number of states is m = = 4. The plaintext given by 11101101 = x0x1x2X3 X4 X5 X6 X 7 when encrypted by the LFSR produced the ciphertext 10000000 = YoY1Y2Y3Y3Y5Y6Y7. What are the tap bits of the LFSR? Please enter your answer as unspaced binary digits (e.g. 0101 to represent P3 = 0, P2 = 1,p1 = 0, po = 1).
PaoBLEM# 3:33 1 Simplify the following Boolean function F(), together with the don't-care conditions d. Express the simplified function in sum of minterms. . F (X, Y,Z) Σm (0 , 1, 2, 4, 5) + Σ d (3, 6, 7) • F(A,B,C, D) = Em(1,3,5,7,9,15) +Ed(4,6,12,13)
2.(a) Consider the use of OTP. Let m be an arbitrary message to be encrypted and c be a given ciphertext in the ciphertext space. How many possible keys with which m can be mapped to c, i.e., f(m,k)=c? None 1 2 The size of the key space Depends on m (b) 3^(-n) is negligible. True or false? (c) n^(-100) is negligible. True or false?
(5) Explain why these are true or false: (a) 31 = 15 (mod 5) (b) 200 = 200 (mod 7) (c) 3785 = 1970 (mod 11)
Algebraic Cryptography] How do you solve this?
(2) (Known plaintext attack for affinc cipher.) Suppose the plaintext starts with if and the corresponding ciphertext is PQ. This means (8, 5) → (15, 16). This gives the simultancous equations 8a + B = 15 (mod 26) ба + В 3 16 (шod 26) Solve this in modular arithmetic to get the keys a = 17, ß = 9.