New answers tagged

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