14

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

The probability of accidentally mistaking a composite for a prime, for a number that you chose yourself, is extremely low and quantifiable, as others have mentioned. This is the situation that is considered in the standard analysis of randomized primality tests. However, there is also a problem of someone maliciously generating a composite that primality ...


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


8

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


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


5

The issue with using Chernick's expression $(6k+1)(12k+1)(18k+1)$ and its generalisations is that the number is always congruent to 1 mod 3 so that twice the number plus one is divisible by and hence not prime. All is not lost however and the methods of Loh and Niebur "A new algorithm for constructing large Carmichael numbers" (which inspired the ...


4

Would [$f_N(x)=x^2\bmod N$] lose the one-way property if $N$ is prime and not a product of two primes? Yes, thanks to the Tonelli-Shanks algorithm (special cases here). [Is] Rabin function still one-way if factorization of $N=pq$ is known? No, because the main ("only") information advantage the private key holder has in the Rabin cryptosystem ...


4

TL;DR There are no standards or RFCs that use this idea. There is a slightly improved number field sieve attack on your example number based on back of the envelope calculations (see below). Your proposed generator would be fine. The follow on proposal should not admit special polynomials for $\ell\ge 768$. The back-of-the-envelope generic attack To attack ...


4

Maybe I miss something, but after some quick thoughts about that algorithm, I think it is not secure. Therefore it may not be used and be more like an example for teaching (with no name). The problem with the algorithm is that you can derive the secret key q from the public key. When you have two integers a and b, where both are a multiple of q (like all q*...


3

I think, it's important to look what is "very small" here : This paper https://exploringnumbertheory.wordpress.com/2014/09/06/an-upper-bound-for-carmichael-numbers/ In the same paper (example 6), it's written that for RSA$-2048$ that the probability a false-positive happens is upper bounded by $\frac{1}{10^{80}}$. I've made the computation with ...


3

You are describing what you might call an "exact GCD" scheme. It is insecure (as discussed in the comments), and I believe the suggested modification to make it secure (add a single error $e$ to all samples) is insecure as well (take 4 coordinates, subtract pairs of them to get $q(a_0-a_1)$, $q(a_2-a_3)$, and then take GCDs. It seems quite likely ...


3

In the pure Quadratic Sieve, we need to find a little more relations (equivalently, smooths) than there are primes in the factor base. In this, we count small primes $p_i$ that make $N$ a quadratic residue modulo $p_i$, not their powers. This count is also the number of columns in the (sparse) matrix of relations, where relations are lines, that serves as ...


3

Little here $a$ and $b$ should be selected from $\mathbb{Z}^*_p$ and $r$ between $1$ and $p-1$ exclusive Looking like this, it seems to relate directly to the DDH problem, at least if there exists some $w$ such that either $a = b^w$ or $b = a^w$. That is if at least one of $a$ or $b$ generates the subgroup containing the other which is a given if $p$ is a ...


3

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

One possible statement of the Discrete Logarithm Problem modulo prime $p$ (the one used in practice in DSA, and more generally when working in a Schnorr group) goes: given large random prime $q$, very large prime $p$ with $p-1$ a multiple of $q$, integer $g$ of order $q$ modulo $p$ (equivalently, such that $g^q\bmod p=1$ and $g\bmod p\ne1$ ), $a$ obtained ...


3

It is a choice of the designers of PGP to stick to Fermat test. There are some nice talk since 1994 sci.crypt: 1994 - Why Fermat test for PGP primes Critique of PGP Key Generation and PGP Attack FAQ: The asymmetric cipher The quote from the last; The Carmichael Numbers Unfortunately, there are some numbers which are not prime and which do satisfy the ...


3

To extend kelalaka's answer, if $p$ is a safe prime (that is, if $p = 2q+1$ with $q$ prime), then: If $p \equiv 7 \pmod 8$, then the order of $g=2$ will be $q$ If $p \equiv 3 \pmod 8$, then the order of $g=2$ will be $2q$ If $p = 5$ (the only other possibility), then the order of $g=2$ is 4 (that is, $2q$)


3

The quote invites computing $5\,P$ on the Elliptic Curve of equation $E:\ Y^2\equiv X^3+3X+7\pmod{11}$ in order to experimentally come to the realization this is the point at infinity $\mathcal O$ (the neutral of point addition), and get the intuition that's why the computation of $5\,P$ on the Elliptic Curve of equation $E:\ Y^2\equiv X^3+3X+7\pmod{187}$ (...


2

Does the use of repeated squaring rather than some arbitrary exponent have any cryptographic significance? Is it just simpler? Mostly, it makes the description simpler. The prover and the verifier jointly compute $g^{2^t} \bmod G$; however they don't don't do it in a balanced way. The prover does the vast bulk of the work, computing all but a factor of $\...


2

Suppose I had an enormous exponent $B$. To compute $g^B\mod G$ (I'll omit "mod $ G$" from now on), I would use a square-and-multiply method: I would compute $g$, $g^2$, $g^4$,\dots, $g^{2^t}$, where $t$ is the bit-length of $B$, then multiply all $g^{2^i}$ for $i=1$ in the binary representation of $B$. Note that this involves, at most, $t$ ...


2

Let's have a look at how these are implemented: RSA RSA is probably the example, showing how prime numbers are used in cryptography. In order to calculate a private key, two prime numbers, $p$ and $q$ are "chosen". What that means in practice is that your computer will generate a random number (and set a few bits) and then check whether or not the ...


2

What exactly is an $n$‑bit number? In the context, number designates an element $m$ of the set $\mathbb N$, the non-negative integers. Such $m$ is $n$‑bit if and only if $n\in\mathbb N$ and $\lfloor2^{n-1}\rfloor\le m<2^n$, or equivalently $n=\left\lceil\log_2(m+1)\right\rceil$. When $n\ne0$, that simplifies to $2^{n-1}\le m<2^n$, or equivalently $n=\...


2

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


2

Not a complete answer, but may already be useful... It is known that only the bit length but not the form of $q$ is important for the security of the LWE (and the RLWE) problem. Moreover, if we can solve $SIS_{n, q, \beta}$ with $\beta = O(q / \sigma)$, then we can solve $LWE_{n, q, \sigma}$ (see Corollary 2 of [MPS15]). Thus, at least for such small bound $\...


2

Is it possible to retrieve the original message $m$ with this information? Well, this is a standard exercise for beginners (that is, you're supposed to learn from it), and so I won't spell out the answer. I will give you a hint: if you know $N, c_1 = m^a \bmod N, c_2 = m^b \bmod N$, can you compute the value of $c_3 = m^{a-b} \bmod N$? If so, how could you ...


2

It is easy to show that in RSA, when e = 3 there are 4 messages m for which the ciphertext is equal to the plaintext and gcd(m, n) = 1 Well, if $m^3 = m \pmod n$ (and assuming $n$ is a conventional RSA modulus, that is, it is $n = pq$, for $p, q$ distinct odd primes), this is equivalent to both of the below holding simultaneously: $$m^3 = m \pmod p$$ $$m^3 =...


1

"Prime factorization" is not worth interest, for primes are their own factorization. Factorization into primes is not used for key generation. I conclude the question asks: When generating primes during generation of public/private key pairs for crytosystems based on hardness of factorization (RSA, Rabin, Pailler…), is there a limit on the size of ...


1

TL;DR This is exactly what is needed for the Fermat factoring method to succeed fast. It is easy to show that $q$ is also within a range of $\sqrt[4]{N}$ of $\sqrt{N}$ up to a little discrepancy. Then, we can approximate $p+q$ as $2\sqrt{N}$: $(p+q) - 2\sqrt{N} = \sqrt{(p+q)^2} - 2\sqrt{N} = \sqrt{(p-q)^2 + 4N} - 2\sqrt{N} = 2\sqrt{N}(\sqrt{(q-p)^2/4N+1}-1)$ ...


1

A large issue with questions like this tends to be the technical details, so apologies if I come across as particularly nit-picky --- I just do not know how to answer questions like this without pointing out the nits that need to be picked. at least if the activation function is continuous, could carry up to even infinitely many links with just changes in ...


1

Can you give me some hints? It's not a proof of knowledge, as someone without knowledge of $x$ can complete this protocol successfully with an honest verifier. Hint: what happens if the ignorant prover sends $y = h^{-1}$?


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