# Break RSA given a correct and faulty implementation

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$.

-

HINT $\$ Consider $\rm\ gcd(A(m)-B(m),\:pq)$

-
Ok, 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. – Steven Oct 8 '10 at 2:48
Consider 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 = ... – Bill Dubuque Oct 8 '10 at 3:02