I am trying to solve congruences of the form $$J_A \cdot a^e\equiv 1 \pmod n$$

where $n=pq$ for $p,q$ prime and $\gcd(e,\varphi(n))=\gcd(J_A,n)=1$

Solve for $a\in \mathbb{Z}$, in terms of $n,J_A$ and $e$.

I am using example from GQ signature scheme from the book Page 451.

Nota Bene: This is not a homework question. I am looking for a way to implement it.

  • $\begingroup$ What are $J_A$ and $e$? $\endgroup$ – orlp Jan 1 '14 at 17:46
  • $\begingroup$ Values of $J_A$ and $e$ are known. I am using example from GQ signature scheme from the book Page 451 cacr.uwaterloo.ca/hac/about/chap11.pdf $\endgroup$ – user5507 Jan 1 '14 at 17:54
  • 1
    $\begingroup$ So did you mean $J_Aa^e \equiv 1 \mod n$, with $n = pq$, $1 < J_A < n$, $0 < e < n, gcd(e, (p-1)(q-1)) = 1$, $gcd(J_A, n) = 1$ and $a \in \mathbb{Z}$? $\endgroup$ – orlp Jan 1 '14 at 17:58
  • $\begingroup$ Yes. It was my mistake $\endgroup$ – user5507 Jan 2 '14 at 1:19

$J_A \cdot a^e \: \equiv \: 1 \:\: \pmod{n} \;\;\;\;\; \iff \;\;\;\;\; a^e \: \equiv \;\; $$\operatorname{modinv}$$(J_A,\hspace{-0.02 in}n) \:\: \pmod{n}$

Since that is the RSA problem, the fastest known way to solve it is to factor $n$ which reveals $\lambda$$(n)$,
and then try $\;\;\; a \: = \: \operatorname{mod}\left(\hspace{-0.03 in}(\operatorname{modinv}(J_A,\hspace{-0.02 in}n))^{\operatorname{modinv}(e,\hspace{.02 in}\lambda(n))},n\hspace{-0.03 in}\right) \:\:\:\:$.


It seems that you are finding a way to solve the RSA assumption.

The RSA assumption says:

If for any probabilistic polynomial time adversary $\mathcal{A}$, that on input $N,e,R $, where $R\in_R \mathbb{Z}_N^*$, outputs $a$ such that $a^e \equiv R\pmod N$ is negligible in security parameter $n$.

Using your way, $R\equiv J_A^{-1} \pmod N$. To solve $a$ is equivalent to solving $a \equiv R^d \pmod N$. So, if the RSA assumption holds, finding the $a$ is no easier than factoring $N$.

But there is a lemma about this:

Let $N,e,d$ be RSA parameters and $f$ be an integer relatively prime to $e$. There is an efficient procedure that given $N,e,f$ (but not $d$) and a value $(a^f)^d \pmod N$ computes $a^d \pmod N$

I'll give a short proof about this lemma:

Proof: from $gcd(e,f)=1$ we have $ve+uf=1$. Let $s=(a^f)^d$, then $\bar{s}=a^vs^u$ is the value we want. Because $\bar{s}^e=a^{ve+uf}=a $, hence $a^d \equiv \bar{s} \pmod N$.

So, my answer is: if you don't want to factor $N$, you can find this value $(a^f)^d \pmod N$ such that $gcd(e,f)=1$.

  • 3
    $\begingroup$ The RSA assumption is just that it's infeasible to find the a, which is logically independent $\hspace{1.15 in}$ of "finding the a is no easier than factoring N". $\;$ $\endgroup$ – user991 Jan 2 '14 at 4:09
  • 1
    $\begingroup$ And in fact the statement should be the other way around, namely "finding $a$ is no harder than factoring $N$". Then as an interesting side note you may say that this is the fastest known method, but it is by no means proven optimal. $\endgroup$ – orlp Jan 5 '14 at 13:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.