# Tagged Questions

An assignment given to a student to be completed outside the regular class period.

Is the following statement true: If $G: \{0,1\}^k \to \{0,1\}^n$ is a PRG, then so is $G':\{0,1\}^{k+l} \to \{0,1\}^{n+l}$ defined by $$G'(x||x')=G(x)||x'$$ where $x \in \{0,1\}^k$ and $x' \in ... 1answer 510 views ### Zero knowledge proof protocol example? Alice is color blind. She never knows if her gloves are matched. Her brother Bob always teases her saying her gloves are mismatched and she should go change them. Alice wants to know if ... 1answer 297 views ### Prove that textbook RSA is susceptible to a chosen ciphertext attack Given a ciphertext$y$, describe how to choose a ciphertext$\hat{y} \neq y$, such that knowledge of the plaintext$\hat{x}=d_K(\hat{y})$allows$x=d_k(y)$to be computed. So I use the fact that the ... 1answer 93 views ### derangements and permutations in cryptography Given a partial key for a mono-alphabetic substitution cipher (missing 11 letters), calculate the number$N$of possible keys, given that no plaintext letter can be mapped to itself. ... 1answer 89 views ### XOR with constant key in CBC mode I have a hypothetical encryption scheme where somebody uses the one-time pad in CBC mode. That is, the block cipher is$E(k, m) :=k⊕m$, and that block cipher is used in CBC mode. Now, I am assuming ... 1answer 80 views ### What is a Message Transmission Scheme? I've been given as an exercise to show an encryption scheme that is CCA-secure but is not a secure message transmission scheme. What is a message transmission scheme, and how does it differ from a ... 3answers 292 views ### RSA assumption and cryptography The RSA assumption states that it is hard to find$m$, given$c = m^e \bmod{n}$,$e$, and$n$(for appropriate choice of$n,e$). Suppose that there exists an algorithm,$D(c,e,n)$, that finds$m$in ... 1answer 120 views ### Is$H(x) = x^2 \bmod p$pre-image resistant, second pre-image resistant and/or collision resistant I have the function$H(x) = x^2\bmod p$, where$p$is a prime of length n bits and this function maps to the message$x$to a n-bit hash value$H(x)$. I need to find out if it is pre-image ... 1answer 133 views ### Given p and q of DSA how do you show they are prime? I am given p = 4916335901 q = 88903 and am asked to show these are prime as well as q|(p-1) in DSA. I am unsure on how to ... 1answer 134 views ### ASCII: weakness Suppose I have an encryption function$e$of a symmetric cipher with plaintext space $$\mathcal{M}=\{1,2,\ldots,2^{24} \}.$$ Now, consider a list$L$of integers: $$67, 114, 121, 112, 116, ... 1answer 275 views ### Break double encryption Let E_k : {0,1}^l be a block cipher encryption function with block-size l and key-length n. In class, we saw that a double encryption with two independent keys E{}'_{k_1k_2}(x) = ... 1answer 166 views ### How is the curve equation used in ECC? I have a hard time learning exactly how the elliptic curve equation is used in the ECC.$$y^2 = x^3+ax+b$$If someone knows and could explain to me in simple steps how this is done or a link to it ... 1answer 274 views ### Calculation of time to crack SHA-256 hash A problem is given: 1 million users are authenticated with 9-digit PIN codes (e.g. 343534643). The PIN values are stored as hash values in a database. The hash is SHA-256, and is computed as: ... 1answer 143 views ### How to prove this LFSR equation? I am having difficulty solving part (ii) of Excercise 5.17 from Becker's Cipher Systems. Exercise 5.17 \quadIf f(x),g(x) are any two polynomials over GF(2) with f(0)=g(0)=1 show that ... 1answer 149 views ### Is differential calculus related to RSA? I'm writing a high school math paper on RSA and I'm wondering if it's possible to relate calculus to RSA. Is calculus used for any part of RSA? It can be for proving equations/theorems, for generating ... 1answer 114 views ### Probability for collisions of a one-way compression function Given a one-way compression function h:\{0,1\}^n \rightarrow \{0,1\}^m and an attacker that picks x_1 \ldots x_t \in \{0,1\}^n (uniformly distributed), I have to show that the probability to find ... 0answers 69 views ### Looking for a detailed example of proof by reduction I'm looking for a very detailed example of proof by reduction. Say we have two or three protocols (that have been proven secure) and we construct a new protocol. We want to provide a proof of security ... 0answers 86 views ### Rabin/RSA four possible messages? Given this encryption method:$$f_{N,e} : Z^{*}_{N} \to QR(N)^{*};\quad f_{N,e}(x) = x ^{2e} \bmod N$$I need to show that, for any x_{0} \in Z^{*}_{N}, there are four elements x \in Z^{*}_{N} ... 1answer 184 views ### How is digital signature different from a message authentication code (MAC)? I know the definitions of both but can't specifically tell how they are different and if one is better than the other. Please help. 2answers 99 views ### Why do some block cipher modes of operation only use encryption while others use both encryption and decryption? In Chapter 6, Question 6.8, of his book “Cryptography and Network Security Principles and Practices”, William Stalling asks: Why do some block cipher modes of operation only use encryption while ... 2answers 2k views ### How to decode an OTP message? First off, I'm extremely sorry if this comes off as a "homework dump", but to clarify, it isn't. I don't want the answer, I want to know how to get to the answer. My cryptography professor gave us an ... 1answer 121 views ### How do I express each element in a field F as a power of a primitive element? I have a field \mathbb F_{2^4}, and it is represented as a residue ring of the polynomials over \mathbb F_2 modulo the polynomial \beta^4 + \beta^3 + \beta^2 + \beta + 1. I want to express ... 2answers 74 views ### Do we need symmetric cryptosystems? One question I had to answer in my crypto exam today was: Do we need symmetric cryptosystems? As it stands, that's probably a debatable question, so I'd like to reformulate this as: Are ... 1answer 139 views ### Prime factorization of RSA modulus Consider RSA public-key encryption with public modulus N=3953. Suppose we know that the public keys e_1=337 and e_2=23 correspond with the decryption information d_1=3385 and d_2=2663. ... 1answer 85 views ### Hill cipher is not perfectly secure I am on cryptography course and there is a homework question to show that Hill cipher doesn't have perfect security. So assume we have an cryptosystem (P,C,K), where P = C = \mathbb Z_{26}^N and ... 1answer 110 views ### Weak Stream Cipher cryptanalysis Hi I have a stream cipher which uses a keystream of: F(r) || F(r+1) || F(r+2) || ... Suppose F(r) is the RSA encryption algorithm: ... 1answer 74 views ### Can a monoalphabetic substitution cipher attain perfect secrecy? Can a monoalphabetic substitution cipher attain perfect secrecy? Definition of perfect secrecy:$${\rm Pr}[\,{\rm Enc}_k(m_1) = c\,] = {\rm Pr}[\,{\rm Enc}_k(m_2) = c\,]$$2answers 117 views ### Why doesn't this dummy mutual authentication protocol provide mutual authentication? I am a student taking a cryptography course so forgive me if this comes off as a silly question. This is an assignment question: ... 1answer 75 views ### how to use salt to sign a message and how is it effective? I've had an assignment to sign a file using hash and salt, so I read about salt and I got why it's important when it comes to password, but not to sign messages. How do I sign something using salt? ... 2answers 146 views ### Breaking Double Encryption I am trying to understand how an attacker knows when he has successfully decrypted a ciphertext for an assignment. As such, some pointers/hints for the following questions would be greatly ... 0answers 30 views ### Generalize the Merkle-Damgard construction for any compression function I am trying to figure out this question: Generalize the Merkle-Damgard construction for any compression func­tion that compresses by at least one bit . You should refer to a general input length ... 0answers 54 views ### A known-plaintext attack on an LFSR-based stream cipher I am reading a book about Cryptography, and I am stuck in a question. I am really trying to solve it for weeks. But I think the problem is I couldn't understand the whole picture. The question was ... 0answers 59 views ### El Gamal encryption scheme and symmetric encryption scheme Consider the El Gamal encryption scheme, a symmetric encryption scheme (KG,E,D), and the following hybrid encryption scheme having an encryption algorithm that, on input a public key (G,q,g,h), where ... 0answers 54 views ### Definition of a Statistical Test In Professor Boneh's online Cryptography course at Coursera, I am a little puzzled by his definition of a statistical test where he writes: A(x) = iff |#0(x) - #1(x)| <= 10.√n Now, if – as ... 0answers 105 views ### What RC4 key value will completely invert S after initial permutation? What RC4 key value will completely invert S after the initial permutation, so that S[0] = 255, S[1] = 254, …, S[254] = 1, S[255] = 0? 0answers 88 views ### Is OAEP reversible? Given nothing more than some integer m = OAEP(M), is it possible to recover the original plaintext M? In other words, without being given the hash functions or the random string used for ... 1answer 249 views ### Is this encryption scheme perfectly secure? Let m = 6, and let \mathbb{Z}_m denote the set \{0,…,m-1\}. Let X \mod m denote the remainder obtained when dividing X by m. (a) Consider the symmetric encryption scheme in ... 3answers 105 views ### Question on RSA trapdoor permutation You plan to use a public-key cryptosystem based on the RSA trapdoor permutation in three different real-life applications, in which the attacker has, respectively, only one of the following resources: ... 1answer 113 views ### Help in understanding exactly how lattices used as one way functions for hashing I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers ... 1answer 107 views ### Partially-known-plaintext attack of a stream cipher based on modular arithmetic I have a function called F, using modular arithmetic as does RSA, defined as$$x\mapsto F(x) = g^x\bmod p$$where$p$is a 1024-bit prime and$g$is a generator of$\mathbb Z_p^*$. A secret key$r$... 1answer 205 views ### Can AES decrypt with a wrong key? The title is asking the question in layman terms, but what I really mean to ask is this: Let$x \in \lbrace 0,1 \rbrace^{128}$(an arbitrary input block) and let$K \in \lbrace 0, 1 \rbrace^{128}$... 1answer 115 views ### Which areas in CS will be (or have been) most affected by fully homomorphic cryptography? I'm in the middle of planning a 5000ish word essay on fully homomorphic cryptography, the current practical implementations and their limitations. Which areas of CS as a subject have been (or will ... 0answers 53 views ### New modulus or new key pair? I have this assignment question that I'm not sure how to answer. Any insight would be helpful. In the RSA public-key encryption scheme, each user has a public key, e, and a private key, d. Suppose ... 0answers 76 views ### m ∈ Zn \Z*n, RSA works but not secure If you happen happen to have a message m ∈ Zn \ Z*n, RSA works but not secure. How likely is it going to happen? |n|=1024 bits |p| = 512 bits |q| = 512 bits. Thanks! 0answers 30 views ### Encryption of numeric value using playfair I am studying in CSE and in my recent exam paper, A question was asked as: Construct a playfair cipher for Plaintext: semester5 and key:technology. Generally as we are taught yet, there is no ... 0answers 250 views ### Question on mono-alphabetic substitution cipher and poly-alphabetic substitution cipher You know that a meaningful plaintext in a language with a 26-letter alphabet, like English, is encrypted using either the mono-alphabetic substitution cipher or the poly-alphabetic substitution cipher ... 0answers 66 views ### Hybrid encryption with Textbook RSA [on hold] A common variant of textbook RSA is the following: During key generation, the modulus$N$is chosen as usual. We chose$e$as$e:=3$(instead of random). Then$d$is chosen with$e\cdot ...
Show that digital signatures under plain RSA are insecure (Plain RSA means that signing is done by calculating $m^d\bmod n$, with $0\le m<n$, and no padding or hashing of $m$). Write an algorithm ...