0
$\begingroup$

Suppose that Alice and Bob use an encryption algorithm based on a one-way function $F$ (Eve knows it), and $r$, a secret key shared between Alice and Bob (Eve doesn't know it). Key is computed as: $K = F(r)||F(2r)||F(3r)||...$, and the ciphertext is computed as $C = M \oplus K$, and all the blocks of $F(r)$ are $1024$-bit long.

If $F(x) = x^e \mod n$, and $(n, e)$ pair is public, will the first $1024$ bits of both plaintext and ciphertext be enough for Eve to read the entire message?

Same for $F(x) = g^x \mod p$, and public $(g, p)$ pair.

Also, are the cases described above good examples of public-key cryptography? But Eve can't encrypt only having public keys, as she doesn't have $r$. So interception of $1024$-bit long plain/cipher pair is the only way for her to obtain some information from the system.

$\endgroup$

1 Answer 1

3
$\begingroup$

This feels like homework, and so I won't give you the answer; I'll give you hints:

If F(x) = x^e mod n, and (n, e) pair is public, will the first 1024 bits of both plaintext and ciphertext be enough for Eve to read the entire message?

If Eve knows the first plaintext $M_0$, and the ciphertext $M_0 \oplus (r^e \bmod n)$, how can Eve recover $r^e \bmod n = F(r)$? Given that, how can she reconstruct $F(kr) = (rk)^e \bmod n = r^e \cdot k^e \bmod n$?

Same for F(x) = g^x mod p, and public (g, p) pair.

Again, given $F(r) = g^r \bmod p$, how can Eve recover $F(kr) = g^{kr} \bmod p = (g^r)^k \bmod p$?

Are the cases described above good examples of public-key cryptography?

Nope; they're not examples of public-key cryptography as all. We know this based on your description:

Suppose that Alice and Bob use an encryption algorithm based on ... r, a secret key shared between Alice and Bob

Public key cryptography doesn't use a secret key shared between the two parties.

Also, please don't describe these algorithms as 'one-time-pad'. That has a very specific meaning (where the pad is generated in a truly random fashion, and not algorithmicly); this is not that.

$\endgroup$
2
  • $\begingroup$ Also, please don't describe these algorithms as 'one-time-pad'. That has a very specific meaning (where the pad is generated in a truly random fashion, and not algorithmicly); this is not that. Thank you, now I see it's incorrect. This feels like homework Unfortunately, it isn't a homework, but a task given on an interview. I didn't get the right answer from the interviewer, but I still want to find it. $\endgroup$ Apr 7, 2016 at 15:11
  • $\begingroup$ thank you again. Just a little bit of math helped to solve it. I was really blind before reading your answer. $\endgroup$ Apr 7, 2016 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.