Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
Hint: Can you find $F(r)$? Then $F(2\cdot r)$? Then solve this problem? –  fgrieu Feb 17 at 14:55
1  
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)$? –  poncho Feb 17 at 15:07
    
@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. –  fgrieu Feb 17 at 15:08
2  
$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$? –  poncho Feb 17 at 15:21
4  
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. –  poncho Feb 17 at 15:32
show 1 more comment

1 Answer 1

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.
share|improve this answer
    
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$ –  user12038 Feb 17 at 16:07
    
1. Well, how do you "create" $c$ given $m$ and $K$? Write this as an equation, and rearrange to learn something useful. –  figlesquidge Feb 17 at 16:34
    
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 –  figlesquidge Feb 17 at 16:36
    
Does $F(r)$ refers to the 1024-bits plaintext-ciphertext pair? –  user12038 Feb 18 at 5:33
    
Well, you might be able to recover F(r) from them..? –  figlesquidge Feb 18 at 9:33
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.