# 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

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 ...

4

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 ...

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

This is purely a counting problem. We want the number $N(n,m)$ of possible permutations of $n$ things, with the constraint that only $m$ among these things can map to themselves ($0\le m\le n$). The values in the question are $n=11$, $m=5$. It holds that $N(n,n)=n!$ (that's the number of permutations of $n$ elements). It holds that ...

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 ...

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

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

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 ...

3

Yes, we need symmetric cryptosystems, for many reasons; to give three of these: We need a hash function to make most asymmetric cryptosystems secure (e.g. we simply do not have a secure signature system based on RSA without a hash), and current hash functions are (or are built from) symmetric cryptosystems. All asymmetric encryption cryptosystems are bound ...

3

In fact the equation is not used directly. If you work in the field of integers modulo $p$, both the $x$ and $y$ coordinates are integers in the $0$ to $p-1$ range, so there are $p^2$ possible points. The equation tells you which points are part of the curve (the $(x,y)$ such that $y^2 = x^3 + ax + b$) and which points are not. In that sense, the equation ...

3

Remark: in One Time Pad the pad is used once, thus this is not OTP, since here $k$ is reused. Hint for part 1: Write the relations between $k$, the message blocks $m_i$, the ciphertext blocks $\small C_i$ with the convention $\small\text{IV}=\small C_0$. Then, find equations that allow computing the desired $m_3⊕m_4$ from known quantities. Hint for part 2, ...

3

That is the general idea of it yes. Some modes of operation (eg CTR) work in such a way that only known values are ever encrypted, forming a stream of pseudo-random data that is then combined with the plaintext by a keyless reversible operation (often xor) to form the ciphertext. Other modes (eg CBC) directly encrypt secret (ie plaintext) values, meaning ...

2

Generally, no. There is no calculus in the design and implementation of the RSA. There are two things that could add some analysis in the whole scheme of things: Maybe involving the Prime Number Theorem, which explains why we won't run out of prime numbers to choose from. Some proofs of the theorem use complex analysis (including the simplest known proof, ...

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, ...

2

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?

2

My own answer would be: 2048, 2048, and still 2048 bits. Why ? Because: 2048-bit is the current "standard recommendation"; it has been so for quite some time, and is likely to remain so for quite some time (decades). See this site for pointers. There are plans for removing support for keys shorter than 2048 bits in some widespread software, e.g. Firefox. ...

2

I'm not sure if your understanding is correct. However, to explain it a bit to be sure you’re on the right track… Some mode of operation only use an encryption function because it is used to generate something to XOR with the plaintext. There is no point decrypt the generated bytes. To decrypt the ciphertext, you just need the same stream of bytes.

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