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$ is chosen randomly from all distinct exponents (ie $\mathbb \{0,\dots ,p-1\}$). The encrypted message is computed using a one-time pad stream cipher, with the keystream computed as $$K=F(r)||F(2\cdot r)\dots$$

How do I decrypt the entire message after obtaining $g$, $p$, and the first 1024 bits of plaintext-ciphertext pair?

  • 1
    $\begingroup$ Hint: Can you find $F(r)$? Then $F(2\cdot r)$? Then solve this problem? $\endgroup$ – fgrieu Feb 17 '14 at 14:55
  • 1
    $\begingroup$ You have the first 1024 bits of plaintext-ciphertext; how can you deduce $F(r)$ from that? If you have $F(r)$, how do you deduce $F(2\cdot r)$? $\endgroup$ – poncho Feb 17 '14 at 15:07
  • $\begingroup$ @Joel Seah: I'm suggesting that you derive $F(r)$; not that you find $r$, which would be a hard problem, known as the Discrete Logarithm Problem. $\endgroup$ – fgrieu Feb 17 '14 at 15:08
  • 2
    $\begingroup$ $n$ and $e$??? You mean $g$ and $p$, maybe? Hint: it turns out you don't really need $g$. And, for extra credit (after you solve this problem), if you don't have $p$, but do have the first 3072 bits of plaintext-ciphertext, how can you recover $p$? $\endgroup$ – poncho Feb 17 '14 at 15:21
  • 4
    $\begingroup$ This is homework, right? Well, you're supposed to learn from homework. Neither fgrieu nor I will give you the answer, because you'll learn by figuring it out yourself. The point of this exercise is not this specific question, but how to think about problems like this. Just consider the hints that we've been giving you. $\endgroup$ – poncho Feb 17 '14 at 15:32

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, some pointers

  1. Given this is a stream cipher, how is $c$ created? In particular, $c=g(m,K)$ for some function $g$. What is this function? Substituting in the data you know, what do you learn?
  2. Write out $F(x)$ and $F(a \cdot x)$. If I tell you $F(x)=y$, calculate $F(a\cdot x)$
  3. Now, consider everything you know. Put it together and finish the problem yourself.
  • $\begingroup$ Thanks for the answer ^^. Err, i just have a couple of questions: 1. $c=g(m,K)$ is the function for encrypting the message right? 2. Would $F(ax)$ be the same as $F(ay)$? Since u told me that $F(x) = y$ $\endgroup$ – user12038 Feb 17 '14 at 16:07
  • $\begingroup$ 1. Well, how do you "create" $c$ given $m$ and $K$? Write this as an equation, and rearrange to learn something useful. $\endgroup$ – Cryptographeur Feb 17 '14 at 16:34
  • $\begingroup$ 2. No it is not. That is something you definitely need to go and look over again, possibly consult your maths texts. You need to expand out F(x)=??? and F(ax)=??? then substitute one into the other $\endgroup$ – Cryptographeur Feb 17 '14 at 16:36
  • $\begingroup$ Does $F(r)$ refers to the 1024-bits plaintext-ciphertext pair? $\endgroup$ – user12038 Feb 18 '14 at 5:33
  • $\begingroup$ Well, you might be able to recover F(r) from them..? $\endgroup$ – Cryptographeur Feb 18 '14 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy