New answers tagged modular-arithmetic
2
If now the prime value $P$ gets increased for constant $k$ (order of $g$ still $k$) does this decrease the security?
No, for random choice of $g$ among $g$ with large constant order $k$.
Why this? If $P \rightarrow \infty$ it would be the normal logarithm ..
When $P$ grows, $g$ also grows. So we never reach the threshold where $g^a<P$. Thus we can ...
1
(I observe $S=c\cdot P$ for some integer $c$.) Is that always the case?
Yes. Proof follows.
If $g=P$ then $S=0$. We'll disregard this special case in the following.
The set $M$ has $k$ elements, with $k$ the lowest strictly positive integer with $g^k\equiv1\pmod P$. This $k$ is known as the order of $g$ modulo $P$. This $k$ divides $P-1$. $M$ also is $\{g^...
1
You've done the hard work by finding that you can obtain $m_i=a_i\,n$ for various (unknown but essentially random) values of $a_i$.
Now define $n_0=m_0$, and compute $n_i=\gcd(n_{i-1},m_i)$ for increasing $i>0$. Sooner rather than later, the $n_i$ will converge to $n$.
This can be proved rigorously (though we often skip rigorous proofs in a crypto ...
1
This smells like a HW question, so the OP should try it with more hints.
By querying this function at $x$, it is easy to tell whether $x\geq n$ or $x<n$. Let $k$ be a natural number such that $2^k<n\leq 2^{k+1}$, how many queries do you need to find this $k$? Knowing this $k$, how can you figure out $n$?
If the modulo operation is part of polynomial ...
3
If you find such you can break RSA.
Assuming the order of c is maximal(likely if c is random ciphertext).
If we have such distinct exponents 𝑎 and 𝑏 they must be equal mod $\lambda(n) = lcm(p-1,q-1)$.
Let the difference between the exponents be $f=b-a$, $f=0\space mod \lambda(n)$
We pick a value e coprime with e, pick a small prime and verify.
We will ...
2
No!
RSA is public-key encryption and in public-key encryption, the known plaintexts are free. Given a public key $(n,e)$ we can find many $(p_i,c_i)$ such that $c_i = p_i^e \bmod n$. If this is a weakness, on the first day it will be broken.
Top 50 recent answers are included
