New answers tagged

0

Great observation! Just a quick recap: $A=g^u\bmod{N},$ where $A$ is the accumulated value, $u=\Pi_{i\in S} x_i$, is the product of the accumulated values $x_i$, where $x_i\in S$ and all accumulated values $x_i$ are primes. An exclusion proof of $x$ is a pair of group elements, $\pi=(g^a,b)$ such that $ax+bu=1$, using the Extended Euclidean algorithm, since $...


2

Question 2 can be easily answered. Yes, an attacker could easily overload this part of the system. This may be the first time S sees A's public key. However, S makes sure the signature checks out, and registers A's new state provided that A's previous state is either older or non-existent. An attacker can easily send their own public key instead of $A$'s ...


14

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


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


0

It’s a nice algorithm, and with careful implementation it can factor N in $O(N^{1/3})$, which is substantially better than the naive $O(N^{1/2})$ trial division. It lets you factor 64 but integers in few milliseconds. It may be the fastest algorithm that requires no deep mathematics, but it’s complicated and takes quite some effort for a talented amateur to ...


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

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


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


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


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


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


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


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

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


0

Standard DHKE Standard DHKE is defined on the multiplicative groups. Alice and Bob agree on the cyclic group $G$ of order $n$ and a generator $g$ then the key agreement is performed as follows; \begin{array}{lcl} \text{Alice} & \text{Transmit} & \text{Bob}\\ \hline a \stackrel{R}{\leftarrow} [1,n-1]& & b \stackrel{R}{\leftarrow} [1,n-1]\\ \...


2

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


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


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


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


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


Top 50 recent answers are included