Suppose I have two machines, $A$ and $B$. $A$ encrypts a message $m$ and outputs the ciphertext $m^e \pmod n$. $B$ outputs $c$ such that $c = m^e \pmod p$ and $c = m^e + 1 \pmod q$. How can I use $A$ and $B$ to find $p$ and $q$? I am allowed to choose $m$ and $n$.
Break RSA given a correct and faulty implementation
0
$\begingroup$
number-theory
prime-numbers
modular-arithmetic
1 Answers
3
HINT $\ $ Consider $\rm\ gcd(A(m)-B(m),\:pq)$
-
0Ok, so I get this: A(M)=m^e+kp and B(M)=m^e+1+jq, k and j are some integers. gcd(A(M)-B(M),pq)=gcd(kp-jq-1,pq). I am stuck here. – 2010-10-08
-
0Consider the value of A(m)-B(m) both mod p and mod q. Since A(m) is (n,n) mod (p,q) and B(m) = (n,n+1) then A-B = ... – 2010-10-08