# Tag Info

7

It is neither pre-image resistant, second pre-image resistant nor collision resistant. It is easy to compute square-roots modulo a prime (assuming, of course, a square root exists, it will half the time). If $p = 3 \bmod 4$, then the simple formula $x^{(p+1)/4} \bmod p$ will work; for $p = 1 \bmod 4$, it's a tad more complicated but still sufficiently ...

7

If you use a concrete-security definition of security for a PRG, then this statement is true. The proof is a good exercise. If you know enough to pose the problem and to understand the definition of security for a PRG, you should be able to find the reduction proof without difficulty. Start by tracing out what the definition is saying. A general comment ...

5

The modulo operator keeps the result of the addition of $M$ and $K$ within the set $Z$. For example, if $m$ is 10, $M$ is 6 and $K$ is 5, $M + K$ would be 11 which is no longer in the set $Z$. Taking 11 mod 10 results in 1 which is in the set $Z$. As a help towards answering the question whether scheme $M + K$ mod $m$ is perfectly secure, when $m$ is 26 ...

5

This is a classical example. Here is the proof system… Bob gives two gloves to Alice so that she is holding one in each hand. Bob can see the gloves at this point, but Bob doesn't tell Alice which is which. Alice then puts both hands behind her back. Next, she either switches the gloves between her hands, or leaves them be, with probability $1/2$ each. ...

4

I am given $p = 4916335901$, $q = 88903$ and am asked to show these are prime To check whether a given integer $n$ is prime you have to check whether it is only divisible by $1$ and $n$, i.e., that it is not a composite integer. If you are given such an integer you can either factor the given integer, use primality tests to check for primality or in ...

4

You should be able to use D for any c by blinding the query to D. Repeatedly try r:=uniformly random in 1..n-1 $x:=D(c\cdot r^e\bmod n, e, n)$ $m:=x\cdot r^{-1}\bmod n$ $c\cdot r^e$ is uniform in the range 1..n-1 (with the possible exception of when c is a multiple of a factor of n, which I haven't checked), so no matter which 1% of c values it is that D ...

4

Since it sounds a lot like homework, I will only give a hint, not the actual answer. First, you don't want to mess with $e$, since you can not be sure that a different $e$ is actually a valid exponent ($e$ has to be coprime to $\phi(n)$, which contains at least $2$ as prime factor). RSA is not IND-CCA. The same attack that works against IND-CCA also works ...

4

A few definitions could assist: are $x$ and $x'$ random elements of $\{0,1\}^k$ and $\{0,1\}^l$? Is $G$ a cryptographically-secure PRG or a PRG with some statistical properties? Let $\mathcal{D}$ be a PPT-distinguisher and $r$ be a uniformly random bitstring of length $k+l$. A common definition (e.g. from Katz-Lindell book) of a PRG includes the following ...

3

The "million usernames" is a red herring, because the user name is used as "salt": the hash value is computed over the password and the user name. When the attacker tries a potential password, he must choose which user name he puts in the hash function; and if a match is found, then this will be for the hash value for this user name only. In other words, ...

3

Background: An infinite sequence $c_0,c_1,c_2,\dots$ is generated by a (linear feedback shift register (LFSR) with) polynomial $f(x) = \sum_{i=0}^n f_i x^i$ if for any $j$, $$\sum_{i=0}^n c_{j+i} f_{n-i} = 0 \text.$$ We can consider the sequence as a power series $\sum_{i=0}^{\infty} c_i x^i$. If we multiply this power series with the polynomial $f(x)$, we ...

3

(The below may be a bit cryptic if you don't know Python.) The idea is not to decode the message, but to manipulate it. Since your ciphertext is C = OTPkey ^ "attack at dawn" all you need to do is to XOR the last 4 bytes of the ciphertext with the original text "dawn" and then again with "dusk", for example: C ^ "attack at dawn" ^ "attack at dusk" ...

3

If you knew $pq$ and $p+q$, you could find $p$ and $q$ by algebra. If you knew $pq$ and $(p-1)(q-1)$, you could find $p+q$. Now $e_1d_1-1$ and $e_2d_2-1$ are both said to be multiples of $\phi(n)$, so their greatest common divisor should be a (smaller) multiple of $\phi(n)$, from which you could easily guess $\phi(n)$. I've probably said too much already, ...

3

I'll expand my comments into a full answer. Start by examining that you know the value of $r^3$ - this is just $F(r)$. You know you can express $F(r+1)$ and $F(r+2)$ symbolically. You can do this for any term in the key sequence, but it will be useful to write down $F(r+3)$. Forget any constant terms in the computations because they can be added in at ...

3

I'm also afraid you couldn't understand this as D.W., but let us start. I sometimes cannot understand your questions. Please restate them, if possible. The definition of the Ajtai hash functions Let $n$, $m$, and $q$ be positive integers. Let $R = \mathbb{Z}_q$ be the quotient ring of integers modulo $q$. Let us define a function, which maps a vector in ...

3

One possibility for what you might be missing: normally the same key (the same matrix) is re-used to encrypt many messages. So now try counting the total entropy in $M$ length-$N$ messages, and the entropy in a $N\times N$ matrix, and compare what happens when $M$ gets large.... Another possibility you might be missing is the consequences of the fact that ...

2

As per request, some hints. Suppose you are an eavesdropper and you intercept the encryption of 'Crypto'. What is the encryption of p? What is the encryption of CopytopCrypto? If we were able to get the message abc...zAB...Z .," encrypted, what messages could we calculate the encryptions of then? $(\dagger)$Suppose you intercepted a later message, which ...

2

If you know the plaintext and the ciphertext, getting the key is trivial. $$c=m \oplus k$$ Try moving the terms around. Hint: $m$ and $k$ can be functionally swapped (change position with each other), ie. only one term needs to be secret. You already know one term. I've pretty much given you the answer. About the decoding procedure: The ASCII table ...

2

An "encryption scheme" defines the encryption/decryption of data. A "message transmission scheme" is about securing transmission and defines both "privacy" and "authenticity" between a sender and a receiver. Since you haven't asked about the definition of CCA-secure (encryption) schemes and since you've been given this as an exercise, I won't mention ...

2

I happened to see some similar question like this. The question mentioned about sending fake signature message. The method is like this: Find some random string R. Use the public key to encrypt the random string R, let the result be X. (R,X) is your signature pair.(Think backwards) When someone verifies the signature, he'll compare {R} with X which are ...

2

Whenever you're trying to attack a scheme that is [algebraically] relatively simple like this one, a sensible first step is to write out everything you know. Now, considering the information you've been given, try and substitute things into oneanother, and see where this leads you. Let $(m,c)$ be the first 1024 bits of the plaintext-ciphertext pair. Now, ...

1

Since this is homework, let me just give you a hint: consider the two-character messages $m_1 = \text{"aa"}$ and $m_2 = \text{"ab"}$. Given a ciphertext $c$ encrypted with a monoalphabetic substitution cipher, can you tell which of $m_1$ or $m_2$ it corresponds to, even without knowing the key? Why (not)? What does this imply about perfect secrecy?

1

To begin with 4: Remember Kerckhoff's principle. You should always assume that the attacker knows which algorithm is used to encrypt your data. All the algorithms used in practice are designed to be secure under this assumption, so you should consider that hiding the algorithm from the attacker is superfluous. But as a hypothetical... I can't think of any ...

1

AES-128 uses the full set $\{0, 1\}^{128}$ as keyspace, and for each key the blockcipher is defined for each input block in $\{0, 1\}^{128}$. The same goes for AES-256, but it uses a 256-bit keyspace (but still a 128-bit block). So the answer to 1 is yes. For 2, we have this equation: $$AES_K(AES_K^{-1}(x)) = x$$ We can decrypt both sides: ...

1

$\left|\hspace{.01 in}\operatorname{Range}(h)\hspace{.01 in}\right| \:$ is the number of elements that the compression function can map to. If $\: m > \operatorname{log}_{\hspace{.01 in}2}\left(\hspace{-0.03 in}\frac{t^2}{2\cdot \epsilon}\hspace{-0.04 in}\right) \:$ then \$\;\; \left|\hspace{.01 in}\operatorname{Range}(h)\hspace{.01 in}\right| \: = \: 2^m ...

1

None. No area of CS has been affected by fully homomorphic encryption yet, because it isn't practical (yet). If it becomes practical, it could have a significant effect on computer security and cryptography, but that remains speculative at this point. Read this answer for more details: http://crypto.stackexchange.com/a/628/351

Only top voted, non community-wiki answers of a minimum length are eligible