Hot answers tagged

75

No. If the claim was true, then there would be an extremely simple way to prove it: $10^{10}$ arithmetic operations is nothing. There are tons of 800-bit factoring challenges available online. The author could just solve them and include the factorization in the submission; the lack of such a straightforward validation should be taken as empirical evidence ...


39

Big issue at the bottom of page 2 where the determinant is quoted as $N^{n+1}\frac{n(n+1)}2 \ln n$ when it should be $N^{n+1} n! \ln n$. If this formula is used directly in the numerical estimates then are likely to be highly inaccurate. UPDATE (5th March): I've taken a bit more time to work through the paper in detail. There's no asymptotic analysis of the ...


23

The error in upper bounding the determinant of the matrix $\mathbf{R}_{n,f}$ by $$N^{n+1} \frac{n(n+1)}{2} \ln N$$ instead of by $$N^{n+1} n! \ln N$$ seems to lead to an error in upper bounding the initial short vector by $$\Vert \mathbf{b}_1 \Vert< \exp(2 \ln n/2)$$ instead of by $$\Vert \mathbf{b}_1 \Vert< \exp(\ln n)$$ which is an exponential ...


19

This question can be summarized: the attacker found a $d$ that did not satisfy $e \cdot d \equiv 1 \pmod{ \phi(n) }$, but it works; what's going on. It turns out that $e \cdot d \equiv 1 \pmod{ \phi(n) }$ is not necessary (it is sufficient). The necessary and sufficient conditions are: $$e \cdot d \equiv 1 \pmod{p-1}$$ $$e \cdot d \equiv 1 \pmod{q-1}$$ If ...


15

We expect that the encryption will fail since the incorrect $\varphi(n)$. Not always; for example, consider the case $p=31$ (a Mersenne prime) and $\bar{p} = 561 = 3 \times 11 \times 17$. We'll set $e = 13$ and $d = e^{-1} \bmod 30 \times 560 = 3877$. Then, if we pick a random message $m=2$, then $2^e \bmod n = 8192$, and $8192^{3877} \bmod n = 2$; ...


15

Kindly, let me know what was the actual problem which leads us to use groups in cyptogrpahy? Well, we use groups and other similar mathematical constructs because: We found there are problems that appeared to be difficult to solve with those groups We found ways to translate the difficulty of solving those problems into the cryptographical strength of ...


15

Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit. This can be easily achieved with existing libraries like; CADO-NFS ; http://cado-nfs.gforge.inria.fr/ NFS factoring: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html Factoring as a service https://seclab.upenn.edu/projects/faas/ The Factoring as a ...


12

What is the exact definition of $x^u\bmod k$? In RSA and most cryptographic contexts, $x^u\bmod k$ is written with: $k$ in the set $\Bbb N^*$ of strictly positive integers. $k$ is the modulus (plural moduli) $u$ in the set $\Bbb Z$ of signed integers. $u$ is the exponent. $x$ in the set $\Bbb Z$ of signed integers, or in the set $\Bbb Z_k$ of integers ...


12

No, it's not proved that solving the RSA problem [that is, finding $x$ from the value of $x^e\bmod n$ for unknown random integer $x$ in interval $[0,n)$, and $(n,e)$ a proper RSA key ] is equivalent to factoring. It's even widely believed that does not hold, for $e$ of fixed magnitude (as used in practice) in particular. Trivially, ability to factor implies ...


12

There is no proof that the integer factorization is computationally difficult and similarly, there is no proof that the RSA problem is similarly difficult. The RSA problem RSA problem is finding the $P$ given the public key $(n,e)$ and a ciphertext $C$ computed with $C \equiv P^e \pmod n$. Factoring $\implies $ the RSA problem This is the easiest part. If ...


11

might have the terminology wrong when I say "GF(2) polynomial multiplication" You are thinking of multiplication in the ring of binary polynomials, that is polynomials with coefficients in the Galois Field with 2 elements. That set is noted $GF(2)[x]$. It's addition reduces to XOR of the coefficients of equal weight. It's multiplication is called &...


10

RSA private key can be found in two ways with $n = p\cdot q$, $p = 11$ and $q = 13$ if Euler's totient function is used as in RSA paper: $$\varphi(n)= (p-1)(q-1) = 120$$ is used then $d = 67 = e^{-1} \bmod 120$ If Carmichael Function used as requried in FIPS 180.4and allowed in PKCS#1 v2.2 standards: $$\lambda(n) = \text{LCM}(p-1,q-1) = 60$$ is used ...


9

I read the question as: Why is it that often, iterating RSA encryption just a few times cycles back to the original value, when the public modulus is $N$ is small? With $N$ square-free and $\gcd(e,\varphi(n))=1$, textbook RSA encryption $$\begin{align}E: [0,N)&\to[0,N)\\ x&\mapsto x^e\bmod N\end{align}$$ is a bijection, equivalently a permutation ...


9

The Prime Number Theorem proves that there are approximately $\frac{x}{\ln x}$ primes less than any positive integer $x$. There are thus about $\frac{2^{2048}-1}{\ln (2^{2048}-1)}-\frac{2^{2047}}{\ln (2^{2047})}=22.8\times 10^{612} - 11.4\times 10^{612}=11\times 10^{612}$ 2048-bit primes. That's a rather large number, since there are only about $10^{80}$ ...


9

TL;DR: it is a matter of conventions and context that $e=1$ is allowed or not. Definitions of RSA vary: The original RSA article asks to first choose the private exponent $d$ as « a large, random integer which is relatively prime to $(p−1)\cdot(q−1)$ », then to compute $e$ as « the “multiplicative inverse” of $d$, modulo $(p−1)\cdot(q−1)$ ». This makes it ...


9

Per the definition of RSA in PKCS#1v2.2 In a valid RSA private key, the RSA modulus $n$ is the product of $u$ distinct odd primes $r_i$, $i=1$, $2$, …, $u$, where $u\ge2$. That makes $n=3\cdot5=15$ the smallest public modulus. and the RSA public exponent $e$ is an integer between $3$ and $n–1$ satisfying $\operatorname{GCD}(e,\lambda(n))=1$, where $\...


8

It sounds like the questions can be summarized as "when a cryptographer writes $\bmod$, what do they mean? Well, it turns out that $\bmod$ has (at least) three subtly different meanings, based on context: It can be a function that takes two integers, and evaluates to an integer. In this context, the expression $a \bmod b$ is that value that can be ...


8

Let $n = p \cdot q $ be product of distinct primes $p$ and $q$, of arbitrary size as in the RSA setup. The RSA public key $(n,e)$ contains both the modulus and the public exponent, so we assume both are known. Let $b = p +q$. If $b$ is also known, then we can form a quadratic equation as $$ f(x) = x^2 - b x + n \label{1}\tag{1}$$ by using the following ...


7

Is this correct? The principles are right, but a number of details are missing. Among these: For RSA "Encrypt the file" can't be with AES only, since that's a 128-bit block cipher, and it would be insecure past 16 bytes. There is an operating mode involved, and likely it involves generation of an Initialization Vector. It's a good idea to use ...


7

I would be surprised that a proper system will work with this; It fails in openssl check. openssl rsa -in sample_rsa_prv_mod.key -check RSA key error: n does not equal p q If you look at an ASN1 parser like ASN.1 JavaScript decoder you will see that your modifications change the modulus. Why the rest didn't corrupt, since the ASN.1 format uses ...


7

Groups have properties which are useful for many cryptographic operations When you multiply 2 numbers in a cryptographic operation you want the result of the multiplication also to be in the same set. For e.g. if you are multiplying something which fits in a byte (or n bytes) by something similar, you also want the result also to fit in a byte (or n bytes). ...


6

There is no known classical algorithm that can factor a 2048-bit modulus in feasible time. Shor's algorithm could do it in feasible time but this algorithm needs to be run on a large-scale quantum computer and as of now there are too many obstacles to create a large-scale quantum computer.


6

What would be the result if $r/2$ was -1? I assume you meant "how does this work if $a^{r/2} \equiv -1$? Yes, that does not give us a factorization; however there's an easy fix - use a different value of $a$. I don't mean "go back to the Quantum Computer and rerun Shor's algorithm with a different base"; instead, select a different value $a'$ ...


6

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including with a modulus much too large to be factored. I'll assume unknown $n=p\,q$ with $p$ and $q$ unknown distinct large primes of comparable order of magnitude, say $\max(p,q)<...


6

What we've got here is a so-called naive implementation, which doesn't consider time complexity of power-then-modulo operations involving large integers. I'd recommend you to read up on square and multiply, exponentiation by squaring, binary exponentiation, for a bit of context. Typical naive implementations have O(2m) complexity, while optimised versions ...


6

From an attacker's perspective, when we have $(n,e)$ and $\phi(n)$, we can compute a working $d\gets e^{-1}\bmod\phi(n)$. It will allow decryption or signature forgery in time polynomial to $\log(n)$: the attacker thus has won. Yet for repeated decryption or signature, the attacker may want to use the Chinese Remainder Theorem for efficiency, just like some ...


6

RSA is almost always used in hybrid mode, where AES (or another symmetric cipher) is used to encrypt the data itself, and RSA is then used to encrypt the random data key. That way RSA has only a static overhead: the modulus size (which is also the key size) in bytes. So for RSA-1024 that would mean an overhead of 128 bytes + whatever overhead is required for ...


6

They are different concepts and have different approaches. AES like any block cipher is a primitive and the encryption is performed by using the block cipher mode of operation. Like ECB,CBC,CTR,GCM,EAX... The pkcs#7 padding or any other padding that is used to fill the last block to the block size with ambiguous remove, not designed for randomization. Even ...


6

First, the Euler's theorem if $n$ and $a$ are coprime positive integers then $$a^{\varphi(n)} \equiv 1 \pmod n$$ where $\varphi(n)$ is Euler's totient function. Take $e> \varphi(n)$. Then, there exists $e' < \varphi(n)$ such that: $$e \equiv e' \pmod {\varphi(n)}$$ Then, we can write $$e = e' + k \cdot \varphi(n).$$ This $e'$ is the smaller ...


6

Although this might not be the solution you're looking for, the Coppersmith theorem offers a simple answer to this. The (general) Coppersmith theorem states: let $f(x)$ be a monic univariate polynomial of degree $d$ with coefficients modulo a positive integer $n$. One can find all integers $x$ such that $|x| \le n^{\beta^2/d}$ and $\gcd(f(x), n) \ge n^{\beta}...


Only top voted, non community-wiki answers of a minimum length are eligible