New answers tagged


Let $\mathbb{Z}, +$ be the group integers, $\mathbb{Z}/n\mathbb{Z}, \times$ the multiplicative group of integers modulo $n$, and $\varphi(n)$ its order. Then $\varphi(n)\mathbb{Z}, +$, the additive group of multiples of $\varphi(n)$ is a subgroup of $\mathbb{Z}$. The function $f : \mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z} : x \mapsto a^x \mod n$ for ...


No, it is not easy! RSA is based on the difficulty of factoring the product $n=pq$ of two large prime numbers. But if you know $\varphi(n)$ for plain RSA you can compute the secret exponent $d=e^{-1}\bmod \varphi(n);\;$ and you can factor $n$ from the two equations $n=pq,\;\varphi(n)=(p-1)(q-1)$.


On trail to follow, from Handbook of Applied Cryptography fact 3.7: Let $n$ be chosen uniformly at random form the interval $[1, x]$. if $1/2 \leq \alpha \leq 1$, then the probability that the largest prime factor of $n$ is $\leq x^{\alpha}$ is approximately $1+ ln(\alpha)$. Thus, for example, the probability than $n$ has a prime factor $> \sqrt(x)$ is ...


I suspect that this might be vulnerable to a combinatorial factoring attack. In this attack, we look at possible solutions to $pq = n \bmod 2^k$, and then extend $p$ and $q$ one bit to list the possible solutions to $pq = n \bmod 2^{k+1}$ Now, if we have no further information about $p$ and $q$, this turns out to be no more efficient than brute force ...


I do not see that the hypothesis helps any of the efficient factorization algorithms: (G)NFS, (MP)QS, ECM, CFRAC, Pollard's p-1, Williams' p+1, Pollard's rho. I do reserve my opinion on Fermat and friends (that is, shortcuts to trial division managing to avoid most candidates), especially after more consideration of the combinatorial factoring attack in the ...


Sure. one-way permutation ​ + ​ strong hard-core functions $\to$ pseudorandom generator $\to$ stream cipher The keystream is concatenation of the strong hard-core function's values at the iterates of the one-way permutation on the key. ​ ( k,f(k),f(f(k)),f(f(f(k))),... )

Top 50 recent answers are included