New answers tagged

2

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


6

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


0

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


2

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


1

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


2

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