Hot answers tagged

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

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


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


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


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


5

I think the question really is: why don't cryptographic libraries generating RSA keys check if $p$ and $q$ are such that $N$ would be easily to factorize by Lehman's method? That's because the probability that this stands are negligible. One way to prove this is to establish that Lehman's method overall has cost $O(N^{1/3})$ for random distribution of $p$ ...


3

I don't understand why is necessary if $p$ and $q$ are known during in generation. Because rsakpv1-basic may be run by something that's not the key generation process; it is there to allow this second party entity to validate things. We generally keep $p$ and $q$ in the private key (along with the other CRT parameters); 800-56B is apparently envisioning ...


3

All is solved in the comments, but I thought this would be a good opportunity to tell a real story. I was once called urgently by a company that I consulted for due to a bug discovered by their QA department. When they encrypted and decrypted with plain RSA, they would sometimes not get the same input back. The problem was simple, they were using RSA1024 at ...


3

In the original Bellcore attack, the attacker needs to obtain a valid signature and a signature where the computation of one of the coefficients is faulty. The exact nature of the fault does not matter, as long as it affects one of the exponentiations. Therefore it doesn't matter how the coefficients are calculated: blinding has no impact on this attack. In ...


2

A small comments: the Damgard-Fujisaki commitment scheme, which you are referring to, does not depend on the strong RSA assumption. If you instantiate it (for example) over RSA group, it is perfectly hiding, and binding under the factorization assumption. However, the soundness of the zero-knowledge protocol for proving relations between integers committed ...


2

Using for example cado-nfs, you can find the factorization (~5min using 32 cores) as 51700365364366863879483895851106199085813538441759 * 3211696652397139991266469757475273013994441374637143


2

Why is that so? Well, we have $m^e \equiv m \pmod n$ if and only if both of the following hold: $$m^e \equiv m \pmod p$$ $$m^e \equiv m \pmod q$$ We know (because of reasoning you accepted) that the number of solutions to the first equation (for $0 \le m < p$) is $\gcd( p-1, e-1) + 1$; we can write out the list as $m_0, m_1, ..., m_{k-1}$ (for $k = \gcd( ...


1

The probabilistic algorithm has (at least part) of it's runtime that follows an approximately geometric distribution. So it can sometime take a long time. In some applications, that's an issue: for excellent reasons, there's almost always some finite timeout to any process, often determined experimentally. Geometric distribution of execution time is a tried ...


1

Given $C$, $M$ and all $k$ public keys, can an attacker tell with significant probability which public key was used to encrypt $M$ giving $C$ ? Well, he can eliminate some of the possibilities (which means with $k=2$, he has a decent chance at finding the correct one). There are two observations he can use: He can eliminate all public keys $K_i$ for which $...


1

The best methods are able to specify 2/3 of the bits of an RSA modulus (see Joye RSA moduli with predetermined portion: techniques and applications) and it is suggested this could save bandwidth. Although the paper has only recently been published, it has been in pre-print form for since 2008 and no one has suggested any direct attacks (Coppersmith's attack ...


1

Consider the similar RSA key generation process: Select a random odd value $z$ between 1 and $2^\ell - 1$; choose $p$ as usual, fix the lower $\ell$ bits of $q$ to $z p^{-1} \bmod 2^\ell$ and chose $q$ with this constraint. Now, this generates RSA keys with the same asymptotic [1] distribution as the standard RSA key generation process. Now, the only ...


1

Are there any cryptographic primitives/protocols allowing the sender to signal to the recipient faster that the message is intended for them, yet not reveal the true recipient to everyone else and allow them to quickly skip trying to decrypt the message? It doesn't appear that the problem of recognizing the message (without leaking who the message is for) ...


1

Let's start with a quick recap of how the RSA cryptosystem works. Essentially, RSA encryption is based on encoding the message as number $m$ and raising that number to some odd power $e$ modulo the product $n$ of two large randomly chosen prime numbers $p$ and $q$. This operation is easy to carry out and in principle reversible, but as far as we know, there'...


1

Yes. More generally, suppose you know the size of the group $\mathbb{G}$ you are working in (RSA, class group etc). Let $A = g^n$ where $n$ is the product of the elements in the committed set. Assuming $n$ is co-prime to $|\mathbb{G}|$, you can compute integers $a_1$, $a_2$ such that $$a_1 x + a_2 n \equiv 1 \pmod{|\mathbb{G}|}\;\;,\;\; |a_2| < |x|.$$ ...


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