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

share|improve this question
    
What are $J_A$ and $e$? –  nightcracker Jan 1 at 17:46
    
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 –  user5507 Jan 1 at 17:54
1  
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}$? –  nightcracker Jan 1 at 17:58
    
Yes. It was my mistake –  user5507 Jan 2 at 1:19
add comment

2 Answers

$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) \:\:\:\:$.

share|improve this answer
add comment

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

share|improve this answer
3  
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". $\;$ –  Ricky Demer Jan 2 at 4:09
1  
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. –  nightcracker Jan 5 at 13:30
add comment

Your Answer

 
discard

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

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