Questions tagged [prime-numbers]
A prime number is an integer greater than 1 with no divisors other than itself and 1. Primes and prime products play an important role in public key cryptography.
366
questions
0
votes
0
answers
31
views
RSA random key generation [duplicate]
How RSA keys are tested for primality if they are random generated? I imagine this could be time consuming task.
4
votes
1
answer
1k
views
Why do Mersenne Twister use Mersenne prime but not regular prime numbers
I'm trying to figure out why Mersenne Twister use exactly Mersenne prime numbers but not regular primes. What makes Mersenne prime numbers more appropriate for this role than regular primes?
- 207
1
vote
0
answers
45
views
Why does sum of remainders of numbers divided by known factors, and repeating the process over and over, give factors of the two starting numbers? [closed]
While working with serial division/remainder method of finding factors, I have found that using knowns such as the known factors of a comparative number, or the difference between a number to be ...
- 11
1
vote
1
answer
62
views
Question about Modified Miller-Rabin Test?
A few months ago I decided to write my own custom prime number generator. One of the tests I use is a modified Miller-Rabin test that tests the number against base 2 and then only tests random odd ...
1
vote
1
answer
80
views
learning with errors
If I talk about efficiency of system of learning with error, is it it fine for q to be composite in Z_q, the ring of integers. As when q would not be prime, Z_q will not be field anymore, won't it ...
- 61
3
votes
1
answer
179
views
Purpose of the b1, b2, b3.... terms in Rabin-Miller Primality Test
In Rabin-Miller primality test, let N be the number you're checking for primality. Here N = 78007.
Let m be the number you get after dividing (N - 1) by 2 several times until you can no longer do so. ...
- 129
3
votes
1
answer
86
views
Big prime factor of the prime number you feed to Diffie Hellman
They say the security of Diffie-Hellman depends on the factorization of (N-1), where N is the big prime number you feed it.
More specifically, (N-1) itself has to have a big prime factor, such as (N-1)...
- 129
1
vote
1
answer
176
views
Rabin-Miller Primality Test - Elaboration needed
In short, my question is:
What exactly do people mean when they say that "The more you apply the Rabin-Miller test to a number, the more certain you can be that the number you're testing is prime....
- 129
0
votes
1
answer
69
views
OpenSSL prime generation
Recently, I have noticed that openssl always gives numbers which have '1' in upper two bits. It always begins with 0xC or higher values (0xD, 0xE, 0xF). It doesn't give primes that starting with 0xB, ...
- 11
4
votes
1
answer
319
views
Discrete Logarithm Challenges and Records
I am wondering whether there are any current challenge problems for Discrete Logarithms.
Specifically in $\mathbb{Z}_p^\ast$ as well as in elliptic curve groups.
It turns out CERTICOM still has some ...
- 21k
7
votes
1
answer
264
views
Generating suitable prime numbers for Paillier key pair in GG18
I am working on MPCs (multi party computation) in crypto, and now I am developing a implementation of GG 18.
In sign phase, algorithm needs MtA (Multiplicative to Additive) and uses a Paillier key ...
- 83
3
votes
2
answers
295
views
EC group order primality test
(Sorry for a newbie question)
In ECC the intent is to create a group of a prime order (or prime multiplied by a relatively small cofactor).
I know there's an algorithm for ECC to count the number of ...
- 339
2
votes
0
answers
35
views
How to find linear complexity of non binary prime fields using berlekamp_massey algorithm in Sagemath?
I am having a prime field of large size (assume it of the type GF(2**18)) and I need to find linear complexity of a sequence (of some specified length) defined on ...
1
vote
3
answers
144
views
Given the existence of provably-hard-to-solve problems, why do we routinely rely on conjectured-to-be-hard problems for encryption?
Let $(X, Y, Z)$ be a set of binary strings of length $n$. Let random $X$ be the private key for encoding (or decoding) message random $Y$ as $Z$. Let the encryption algorithm $m$ be a matching ...
- 139
1
vote
1
answer
76
views
RSA - plaintext equal ciphertext
Just started learning about RSA cryptography so forgive me if I made any mistakes or misunderstandings.
...
1
vote
0
answers
316
views
How can I decrypt a message with RSA if $e = 65536$ and $\gcd(e,\phi(N)) = 8$?
In a message exchange with RSA, an unusual public exponent $e = 65536$ is used.
Since $N$ is easily factored, I am able to derive $p$ and $q$. Consequently $ \phi(N) = (p-1)*(q-1)$.
However, since $2^...
- 33
3
votes
1
answer
508
views
Quickest way to find MD5 collision
I'm trying to find a MD5 hash collision between 2 numbers such that one is prime and the other is composite (at most 1024-bit). I'm using fastcoll with random prefixes for each iteration.
For this I ...
- 161
2
votes
1
answer
106
views
What bitlength should I use for generating primes for a ElGamal Encryption Cyclic Group (given the data to encrypt has a short time-value vector)?
I am generating large prime numbers to create a cyclic group for ElGamal encryption, I can specify the bit-length n but want to limit the size because this will ultimately allow me to limit the amount ...
- 71
2
votes
1
answer
96
views
Iteration count for (enhanced) Miller-Rabin
In FIPS 186-5 (Digital Signature Standard or DSS) there is a Table B.1 which specifies the minimum number of rounds of Miller-Rabin testing for 1024, 1536 and 2048 bit keys, used for digital ...
- 91.2k
2
votes
2
answers
127
views
Verification through prime modulus
Asking this question here since it has a flavor similar to some cryptographic protocols. How likely are two integers which are smaller than some threshold, mod by some prime number to have the same ...
- 123
1
vote
1
answer
142
views
Proving the generator criterion for group $Zp$
I am trying to understand how to find a generator of Zp. How to find generator $g$ in a cyclic group?.
I have heard that we can pick random a Zp and for each primitive d| p-1 check wether:
a^[(p-1)/...
- 173
2
votes
1
answer
65
views
What is the purpose of "q" in Safe Prime definition during key pair generation?
Consider the following case, given x(private key) and y(public key), how to determine whether this key pair is generated by a pre-defined Safe Prime Group(Say FFDHE, RFC 7919)?
In context of SP800 ...
- 33
2
votes
2
answers
138
views
A variation of Sieve of Eratosthenes for random pseudoprime number generation
I wasn't sure if this question is more suited for SE.Math or not; please tell me if I should move it.
For its mpz_nextprime() function (find the next pseudoprime ...
- 289
14
votes
3
answers
1k
views
Why does GMP only run Miller-Rabin test twice when generating a prime?
In mpz_nextprime(), after some sieving with small primes, an MR test function is called, with the number of trials set to 25 (https://github.com/alisw/GMP/blob/...
- 289
2
votes
1
answer
235
views
RSA: exploiting consecutive primes
It's given 2 plaintexts $m_1$ and $m_2$, and 5 different values of $n\quad\{n_1, n_2, n_3, n_4, n_5\}$ which are generated as follows:
$n_1$ is a a product of two relatively small 128-bit $p$ and $q$ ...
- 21
2
votes
1
answer
113
views
Significance of having remainder $3$ when divided by $4$ for both $p$ and $q$ in BBS
In the Blum Blum Shub random number generator, we take two random prime numbers $p$ and $q$ such that both have a remainder of $3$ when divided by $4$. My question is why can't we just take any $2$ ...
- 21
2
votes
1
answer
93
views
What happens if the Miller-Selfridge-Rabin-Test fails
MRT is a probabilistic test and even the deterministic version relies on the correctness of the Riemann hypothesis.
When the test fails and I use a non-prime number in e.g a public key encryption ...
- 123
9
votes
1
answer
255
views
Does a 2047-bit factoring oracle affect 2048-bit RSA security?
I started wondering. RSA relies on prime factorisation being hard. So if a 2047-bit oracle machine existed that could instantly factor any 2047-bit number (and you can't look inside at how it works), ...
- 191
4
votes
2
answers
1k
views
Are there prime numbers that are easy to modulo within 40 bits to 60 bits?
I want to implement LWE-based encryption scheme, the modulo $q$ could be decomposed as $q = q_0\cdot q_1\cdots q_k$ according to CRT. I guess the modular arithmetic by $q_i$ is key operation, so I ...
- 499
0
votes
0
answers
97
views
RSA: Obtain private key exploiting badly generated public key
I have to solve the following problem:
What I have:
$n$, a 2048 bit number
What I need to find:
$p$ and $q$ such that $n = p\cdot q$.
What I know:
With $p_1$ the first half of $p$ and $p_2$ the ...
- 1
1
vote
2
answers
119
views
Factorization of the product of two specific primes
Help me please.
Consider specific primes $p = x^{d} + 1$ and $q = x^{e} + 1$ for some $x, d, e \in \mathbb{N}$. Can their product $n = pq$ be factorized faster than the product of general primes ? In ...
- 365
1
vote
1
answer
51
views
Division by $2$ or principal root with DH oracle
Assume $g$ is generator of multiplicative group modulo prime $p=2q+1$ where $q$ is prime.
Assume we know $g^{2t}\bmod p$ and $g^{2}\bmod p$ and assume we can have access to a Diffie-Hellman oracle.
...
- 908
5
votes
0
answers
307
views
Average false-positive rate for a round of Miller–Rabin
I'm aware that the Miller–Rabin primality test will claim primality for a composite number with at most a $\frac{1}{4}$ probability for some arbitrary, odd composite $n$ and a random witness $a$ ...
- 15k
1
vote
1
answer
133
views
On access to a Diffie Hellman oracle
Assume $g$ is generator of multiplicative group modulo prime $p$.
Assume we know $g^X\bmod p$ and $g^{XY}\bmod p$ and assume we can have access to a Diffie-Hellman oracle.
Can we find $g^Y\bmod p$ in ...
- 908
0
votes
1
answer
124
views
Breaking RSA with knowledge of the secret key $(n, d)$
I am following the discussion in Koblitz in the second paragraph in the RSA section (page 94 on my edition).The goal is to show that knowledge of an integer $d$ such that $$m^{ed}\equiv m \mod n$$ for ...
3
votes
0
answers
289
views
Elliptic Curve how to calculate y value [duplicate]
I have been reading the book Mastering Bitcoin written by Andreas. It was the process of compressing public keys that hurt my mind. Specifically, a public key after being generated from a private key ...
- 85
1
vote
0
answers
33
views
Finding an element of $\mathbb{Z}_p$ if the order of that element is known [duplicate]
I have two prime numbers $p$ (1024 bits) and $q$ (160 bits) such that $q$ divides $p-1$. Now I want to find an element $b$ in $\mathbb{Z}_p$ with the order of $q$. That means that $b^q \equiv 1 \mod p$...
- 11
-1
votes
1
answer
144
views
Why doesnt RSA use composite numbers?
I am currently writing a math paper regarding the importance of prime numbers in RSA encryption. I understand that generating q x p = N (where p and q are prime numbers) is simple for a computer ...
2
votes
2
answers
190
views
How much work to find such $n$?
Let $W$ be a random $200$ bit number. How much work would it take to find a semiprime $n=p_1\cdot p_2$ such that $p_1,p_2 > 2^{50} $ and $|W-n|<2^{12}$?
More generally, let $W_b$ be a random ...
- 23
3
votes
1
answer
432
views
Given $φ(n)$ how can we find any combinations for $p, q$ prime numbers
Suppose i already have found that $φ(n) = 240$ for $n = 900$. How can i conclude that my $n = pq$ is of type $2^2\cdot3^2\cdot5^2$?
What is $q$ and what is $p$ here?
To be more precise with my ...
- 133
1
vote
0
answers
261
views
Building an Adversary for a PRF game
Here is the game:
How can I make an $\mathcal{O}(k^2)$-time adversary making only one query to its Fn oracle and achieving advantage $= 1 - 1/(p-1)$
Here is my idea so far:
query $2^{-1}$, which when ...
- 21
1
vote
0
answers
72
views
Which of the following is considered cryptographically hard/easy?
Which of the following are easy, if any? Which are hard? and why.
Case 1) Given $x^3 \bmod N$, where $N$ is a composite number and we don't know any of the factors of $N$, find $x$.
Case 2) Given $x^...
- 21
0
votes
2
answers
388
views
The number of odd integers we have to test until to find one that is a prime for any arbitrary RSA modulus size
Popular RSA modulus sizes are $1024$, $2048$, $3072$ and $4092$ bit. How many random odd integers do we have to test on average until we expect to find one that is a prime?
I know roughly every $\ln p$...
6
votes
1
answer
237
views
Finding large devious primes
Call a prime $p$ devious if $(p-1)/2$ is a Carmichael number. They are called devious since they superficially look like safe primes but are not. In particular, Diffie-Hellman using such a prime could ...
- 362
1
vote
1
answer
579
views
Specific case of RSA where cipher text equals plain text
How did they arrive at the conclusion that there are 4 messages where plain text equals cipher text from "It is easy to show that in RSA, when e = 3 there are 4 messages m for which the ...
- 11
1
vote
1
answer
89
views
The significance of the field of the factor in Lenstra’s ECM
I am going through Lenstra's Elliptic Curve Factorisation from Silverman's Mathematical Cryptography book.
I have understood the algorithm itself, but unable to understand a specific point the book ...
- 2,167
0
votes
1
answer
163
views
Setting up the discrete logarithm framework
The discrete logarithm problem over prime cyclic groups consist of finding $x$ satisfying $g^x\equiv h\bmod p$ where $g$ is generator of multiplicative group $\mathbb Z/p\mathbb Z$ at a large prime $p$...
- 908
2
votes
2
answers
126
views
Constraints on q for q-ary lattices?
In lattice cryptography, people often work with q-ary lattices so that we can use the hardness of short integer solution (SIS) and learning with errors (LWE). I saw in some notes that sometimes we ...
- 155
2
votes
0
answers
79
views
What would be the safety requirements for the primes in $n=p \cdot q$ regarding the factorization?
Let it be $p, q \in \mathbb{P}$ with $p,q \in [2^{b-1}, 2^b]$ for some $b \in \mathbb{N}$ and $p \cdot q = n \in \mathbb{N}$. What would be the distance between $p$ and $q$ (as a function of b) so ...
- 53
2
votes
1
answer
400
views
Quadratic Sieve: Is there a thumb rule for deciding how many numbers to sieve?
In the Quadratic Sieve algorithm, we first decide on a B & then look for B-smooth prime factors by sieving using a quadratic polynomial.
I can find a few formulas which help figure out how to ...
- 2,167