0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Hint: Can you find $F(r)$? Then $F(2\cdot r)$? Then solve this problem? $\endgroup$
    – fgrieu ♦
    Commented Feb 17, 2014 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
    Commented Feb 17, 2014 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 ♦
    Commented Feb 17, 2014 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
    Commented Feb 17, 2014 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
    Commented Feb 17, 2014 at 15:32

1 Answer 1

Reset to default
2
$\begingroup$

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.
Improve this answer
$\endgroup$
6
  • $\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
    Commented Feb 17, 2014 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
    Commented Feb 17, 2014 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
    Commented Feb 17, 2014 at 16:36
  • $\begingroup$ Does $F(r)$ refers to the 1024-bits plaintext-ciphertext pair? $\endgroup$
    – user12038
    Commented Feb 18, 2014 at 5:33
  • $\begingroup$ Well, you might be able to recover F(r) from them..? $\endgroup$
    – Cryptographeur
    Commented Feb 18, 2014 at 9:33

Your Answer

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