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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
120 views

How to know if a random number is a probable semiprime?

Simple question : given a randomly generated number $N$ from a hash that is hard to factor, how to check if $N$ is probably a semi‑prime in a faster way than factoring it ? My problem is while it’s ...
user2284570's user avatar
5 votes
1 answer
1k views

Intentionally craft a 180 to 255 bits Integer that bypass this miller‑rabin test with having a known factor

I’ve a signature system using modular exponentiation where having the exponent being a composite with a known factor allows to forge signatures… In order to check if the exponent is a prime number, ...
user2284570's user avatar
1 vote
1 answer
203 views

Could FIPS 186-5 A.1.6 method generate P and Q with different bit size?

refers to FIPS 186-5 document, I have a question about RSA Key generation A.1.6 method, "Generation of Probable Primes with Conditions Based on Auxiliary", my understanding is that, this ...
gx16's user avatar
  • 45
3 votes
1 answer
186 views

Testing whether the Euler Totient of a number equals to certain value

I have solved a problem in Project Euler. My solution was based on the finding the all numbers whose Euler Totient value equals to $13!$ However, while I was working on the problem, I thought that: &...
NB_1907's user avatar
  • 640
1 vote
0 answers
98 views

Number of elements in cyclic group that satisfy an exponent

I'm having trouble with solving the following question: Given two distinct prime numbers $p, q$ where $(p-1)$ and $(q-1)$ are not divisible by $3$, define $n=pq$. For how many elements in $\mathbb Z^*...
Eatay Mizrachi's user avatar
1 vote
1 answer
69 views

How zetas are computed in CRYSTALS-Kyber?

As shown below it explains how generate zetas table and use it. But curious thing is that how KYBER_ROOT_OF_UNITY constant is generated ? I've tried multiple ways to generated it and cannot explain ...
Ali ÜSTÜN's user avatar
0 votes
1 answer
51 views

Compute a proof for a verifiable delay function

I am trying to solve the following problem: Alice generates a RSA key $(n, \phi)$, she shares with Bob the value $n$, and $y = g^{2^{t}}\;\text{mod}\; n$ for $g$ a generator of the group $\left(\...
Kroki's user avatar
  • 111
1 vote
1 answer
114 views

Why are the primes all the same size in pqRSA?

pqRSA is MP-RSA with 4096-bit primes to build up a modulus of up to 1TB. If the objective is to make processing the modulus as expensive as possible for the quantum computer why not use just two 4096-...
user avatar
0 votes
0 answers
83 views

Generating a new curve using an existing curve and new prime

Can you take a curve equation from https://safecurves.cr.yp.to and a large safe prime from existing DH parameters (for example openssl dhparam 9000), combine them, ...
user avatar
2 votes
3 answers
220 views

Is any safe prime sufficient for a secure DH key exchange?

There are some very large safe primes listed here: https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes Would using any of them result in a secure DH construction? Generator is 2. The exponent ...
user avatar
0 votes
1 answer
141 views

Is a prime shifting method for RSA modulus generation safe?

I have a prime number, $p$, with $n$ bits. To generate a new prime number, $q$, I shift the bits of $p$ from left to right by a certain length. For example, if $p$ is represented as ...
Lisbeth's user avatar
  • 497
3 votes
2 answers
552 views

RSA perfect square phi

So I've been learning about RSA for quite a while (mainly by playing around in CTF competitions) and I came across an interesting problem. The other day I was looking to create a challenge in which I ...
Anonymous's user avatar
0 votes
2 answers
353 views

Are Safe and Sophie Germain primes evenly distributed?

Do Safe and Sophie Germain primes maintain a relatively stable distribution as numbers get larger, or do they become rarified beyond a predictable value? This is important in one area of triangular ...
Zekchelovek's user avatar
1 vote
1 answer
371 views

DHKE: Why using safe prime gives us "safe" subgroups?

I come from the question here: Safe primes subgroup in Diffie–Hellman key exchange Where the accepted answer states that there are only 4 possible outcomes for the order of a subgroup when using a ...
Ymi's user avatar
  • 175
1 vote
1 answer
80 views

Is gcd(e,p−1)=1=gcd(e,q−1) similar to gcd(e,phi(n))=1?

I wonder, is $\gcd(e,p−1)=1=\gcd(e,q−1)$ similar to $\gcd(e,\phi(n))=1$ ??
Nicha59's user avatar
  • 11
1 vote
0 answers
96 views

Is there any harm using a pseudo-prime endorsed by a probablistic test like Miller-Rabin in RSA?

In RSA, the decryption exponent $d$ is typically calculated as $$d= e^{-1} \bmod{(p-1)(q-1)}$$ or $$d = e^{-1} \bmod \operatorname{lcm}{(p-1, q-1)}$$ where $p$ and $q$ are often randomly selected ...
DannyNiu's user avatar
  • 9,207
0 votes
1 answer
152 views

Safe primes subgroup in Diffie–Hellman key exchange

I'm trying to understand how the safe primes numbers are used in Diffie–Hellman key exchange. According to wiki: The order of G should have a large prime factor to prevent use of the Pohlig–Hellman ...
pacman's user avatar
  • 429
2 votes
1 answer
94 views

Properties of Sums of Legendre Symbols

Context An unknown modulus N with 8 unknown prime factors $p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8$ a plaintext $m$ is encrypted with the formula $c = 2^m \mod N$ the only things the attacker know are ...
Cukurukuk's user avatar
0 votes
1 answer
244 views

RSA - Twin Primes across two messages

This was a CTF challenge I was unable to solve, but I thought I may had come close. We were given two $N$'s $N_1$ and $N_2$ each calculated with $P_1 \times Q_1$ and $P_2 \times Q_2$; however, $P_1 = ...
Nasica's user avatar
  • 1
0 votes
0 answers
53 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.
sergiu malutan's user avatar
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?
pacman's user avatar
  • 429
1 vote
0 answers
54 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 ...
JohnBlack's user avatar
1 vote
1 answer
77 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 ...
Daniel Gonzalez's user avatar
1 vote
1 answer
135 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 ...
user479610's user avatar
3 votes
1 answer
188 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. ...
Kevin Stefanov's user avatar
3 votes
1 answer
127 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)...
Kevin Stefanov's user avatar
1 vote
1 answer
609 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....
Kevin Stefanov's user avatar
0 votes
1 answer
134 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, ...
Sukru's user avatar
  • 11
5 votes
1 answer
481 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 ...
kodlu's user avatar
  • 22.5k
7 votes
1 answer
284 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 ...
user109261's user avatar
3 votes
2 answers
304 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 ...
valdo's user avatar
  • 339
2 votes
0 answers
40 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 ...
Mathpdegeek497's user avatar
1 vote
3 answers
156 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 ...
virtuolie's user avatar
  • 139
1 vote
1 answer
100 views

RSA - plaintext equal ciphertext

Just started learning about RSA cryptography so forgive me if I made any mistakes or misunderstandings. ...
Lykos Angiolo's user avatar
1 vote
0 answers
512 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^...
Jake's user avatar
  • 33
3 votes
1 answer
970 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 ...
infinite-blank-'s user avatar
2 votes
1 answer
115 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 ...
Poseidon's user avatar
2 votes
1 answer
148 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 ...
Maarten Bodewes's user avatar
  • 92.6k
2 votes
2 answers
129 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 ...
Sam's user avatar
  • 123
1 vote
1 answer
268 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)/...
tonythestark's user avatar
2 votes
1 answer
80 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 ...
gx16's user avatar
  • 45
2 votes
2 answers
154 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 ...
fjarri's user avatar
  • 289
14 votes
3 answers
2k 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/...
fjarri's user avatar
  • 289
2 votes
1 answer
435 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$ ...
Alden Luthfi's user avatar
2 votes
1 answer
152 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$ ...
swarna islam's user avatar
2 votes
1 answer
124 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 ...
Hartmut Braun's user avatar
9 votes
1 answer
266 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), ...
Christer's user avatar
  • 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 ...
Bob's user avatar
  • 509
0 votes
0 answers
104 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 ...
Uri's user avatar
  • 1
1 vote
2 answers
130 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 ...
Dimitri Koshelev's user avatar

1
2 3 4 5
8