Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
22 views

Problem with Chaum`s Untraceable Electronic Cash

For example according to protocol I need calculate this: $b=F^{(1/h)} \bmod pq.$ Where $p$ and $q$ are prime numbers. I have $F$ and $h$. But how can I calculate $b$? I tried to do this: $\text{...
2
votes
1answer
34 views

Lenstra's ECM Algorithm - field requirement

In Lenstra's ECM algorithm, $\#E(\mathbb{F}_{p})$ is required to have small prime factors. Why is this so? I understand that the p-1 method is efficient for factoring N with small factors. The ECM ...
4
votes
3answers
553 views

How to verify if g is a generator for p?

For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)
2
votes
0answers
65 views

Is it possible to check if a number is the product of two primes without factorizing it?

I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox). I have started to run a factorization algorithm on it, and after a few hours ...
0
votes
1answer
85 views

Does a Finite Field of 36 elements exist? [duplicate]

I'm having a little trouble understanding the finite fields theory, so I'm sorry if my question would seem a little stupid. I wanted to know if a finite field of 36 elements could exist. Basically, I ...
3
votes
1answer
138 views

Fermat's factorization method on weak RSA modulus

Given a public key for RSA, I have extracted the modulus which looks like this: ...
0
votes
0answers
72 views

Yukel's Sieve - Factorization of Numbers into a Square Sieve

https://www.youtube.com/watch?v=liTTGeitpGQ https://www.youtube.com/watch?v=2nOwgiweyqc https://www.youtube.com/watch?v=rGwFsOG27DQ I came across these videos explaining a pattern that is found in ...
7
votes
1answer
132 views

Distinguishing generators of RSA primes and moduli

We are trying to distinguish two RSA prime generators: Prime generator 1 draw uniformly at random an integer $p$ with $2^{1023.5}<p<2^{1024}$, until it is prime output $p$. Prime generator 2 ...
3
votes
2answers
85 views

Are relatively prime numbers used in RSA

We know that the Totient function is multiplicative. Which means that when $p$ and $q$ are relatively prime, then $\varphi(p q)$ is equal to $\varphi(p) \varphi(q)$. My question is, are only prime ...
4
votes
1answer
282 views

How does Python's pycrypto library generate primes?

The pycrypto library in Python can generate random n-bit prime numbers. The syntax I use is as follows: from Crypto.Util import number number.getPrime(2048) The ...
4
votes
1answer
88 views

Magic Number to calculate number of rounds for M-R in FIPS 186-4

In Fips 186-4, there is an algorithm in Appendix F (at page 117 in my copy of the 2013 version) to calculate the number of rounds of the Miller-Rabin primality test to random bases. Does anybody ...
1
vote
0answers
40 views

Random Primes Conjecture [closed]

I know it is believed that primes appear to be randomly distributed among the integers. Is there a formal conjecture or theorem that expressly states that the occurrence of the prime numbers is ...
1
vote
1answer
79 views

How can I generate large primes for Pedersen commitment?

I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing". To implement the commitment ...
4
votes
2answers
393 views

How to efficiently generate a random safe prime of given length?

A prime $p$ is said to be safe prime if $(p-1)/2$ is also a prime. How to efficiently generate a safe prime? I have written the following code in sagemath which generates a random safe prime of 1536 ...
1
vote
1answer
92 views

DSA: How to calculate 224-bit $q$ for 2048-bit $p$

$p$ is a 2048 bit prime number $q$ is a 224 bit prime number I know that $q$ is a prime divisor of $p-1$, thus $p=1 \bmod q$ but I couldn't write efficient code to calculate this. I can calculate ...
1
vote
1answer
59 views

How to formally say that the integers modulo $p$ for a prime $p$ gives results that are “more random” than for a composite $n$?

I'm doing a presentation on cryptography for non-experts. My main algorithm of the presentation is the Diffie Hellman key exchange. It uses modulo arithmetic for a prime $p$. During my presentation, I'...
-1
votes
1answer
108 views

Swift and (very) large integers [closed]

I am trying to write a simple Mac program to factor primes. Nothing new, but I have a problem. The largest integer I can use seems to be 2^64, which is not that big. Did you hit any similar problem? ...
1
vote
1answer
209 views

RSA finding p and q integer with condition

I'm given $N=p\,q$ and told that $44\,p\approx 17\,q$ (with the value given for $N$ some 49-digit integer 8124642558124642555899928124642555899924479992447). In ...
-1
votes
1answer
57 views

What is the difference between these cyclic groups

$\mathbb{Z}^*_p$ vs $\mathbb{Z}^*_{p-1}$ vs $\mathbb{Z}^*_{p^2}$ vs $\mathbb{Z}^+_{p^2}$ I know $p$ is the value. The value create must be coprime to $p$. Does that mean that the value create must be ...
3
votes
1answer
235 views

How big are the primes used in modern cryptography?

I know that this depends on which techniques you're using, but roughly speaking, when modern cryptography makes use of so-called "large prime numbers", how large (in bits or digits) are these primes ...
1
vote
2answers
121 views

In RSA, is it possible to compute the private key if one knows one of the primes used to generate n?

Within RSA the private key can be derived if one knows both $p$ and $q$. Is it possible to derive the RSA private key or decrypt / learn something about encrypted messages if you only know one of the ...
3
votes
3answers
2k views

Can multiplication of two primes be seen as a strong cipher?

If we were define such a cipher: A reversible function that would accept a message $M$ and an initialization vector $\text{IV}_1$ $\operatorname{map}(\text{IV}_1, M)$ which can map an input $M$ to a ...
0
votes
2answers
76 views

Public-key generation - primes reuse

Given the following Trap-door Commitment scheme Secret key receiver: $x_B \in_u Z_q$ Public key receiver: $y_B = g^{x_B} \mod p$ Here, $p=q*k+1$ for two primes $p,q$ and $k \in Z$. And $g$ is the ...
2
votes
1answer
195 views

Efficient algorithm for finding Sophie Germain primes

What's the industry standard for an efficient finding large Sophie Germain primes? As a part of request handling in my application, I need to generate Paillier key. My current approach is to ...
14
votes
2answers
526 views

RSA factorization for special primes $p$ and $q$

I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given): $$p = a^2 + b^2, \...
4
votes
0answers
215 views

Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
-1
votes
1answer
176 views

Does Parallax Compression endanger cryptography?

http://www.novaspivack.com/science/we-have-discovered-a-new-pattern-in-the-prime-numbers-parallax-compression A lot of cryptographic algorithms depends on prime numbers. Will this influence any ...
4
votes
1answer
63 views

Lightweight primality certificates for untrusted DH parameters

Are there any light-weight techniques to generate primality certificates for custom Diffie-Hellman parameters that could be sent to the client to allow it to verify primality without needing to run ...
-1
votes
2answers
165 views

A quick way to justify whether $a^m \equiv 1 \pmod{n}$?

Say I would like to justify whether $10^{28} \equiv 1 \pmod{29}$. I know according to Fermat's little theorem that $a^{p-1} \equiv 1 \pmod{p}$ when $a$ is a primitive root modulo $p$. What about ...
0
votes
2answers
113 views

Why is prime factorisation computationally intensive compared to normal factorisation?

Why do we use prime factors in asymmetric algorithms compared to other factors? For example: lets say we use two prime numbers p = 53 and q = 59 our public key in RSA algorithm would be p * q =...
1
vote
1answer
226 views

Example of calculating a primitive root for large prime?

I am trying to figure out how to calculate primitive root $w$ for a prime. Following what I read, I generated my prime to be 'safe prime', $p=qr+1$. I know $q$ (also prime) and $r$. Let's assume, ...
3
votes
1answer
56 views

Can we efficiently factor if we are given a Pocklington certificate of one of the prime factors?

I recently read Squeamish Ossifrage's answer on generating RSA keys from (short) randomness where they make the following comment: (You might want to keep the certificate secret too.) As the ...
0
votes
4answers
280 views

Finding the prime factors of $n'$ given the previous $n$ and its prime factors $p$ and $q$

Say I have a very large number $n$ = $pq$ where $p$ and $q$ are prime. A new number $n'$ is generated by increasing these prime factors. How can I find this new number's prime factors?
0
votes
1answer
40 views

Breaking a modified version of Diffie Hellmann Protocol

I'm modifying the Diffie Hellman protocol as follows: We are given a large prime number $p$ and exponent $x$ such that $0 \lt x \lt p-1$ and $\mathrm{gcd}(x, p-1) = 1$. Also we pick $g$ such as $1 \lt ...
1
vote
1answer
501 views

How to find the public key in RSA?

Finding the public key given the private key $d$ and the prime numbers $p$ and $q$. $$p = 3092551601$$ $$q = 3490383433$$ $$d = 10719928016004921607$$ Since this is RSA, here is my thinking. In ...
-1
votes
2answers
83 views

Understanding reversible addition in a prime field

I'm trying to understand the security implications of addition in a prime field. Suppose I have X + Y = Z, occurring under prime field P(W) where W is the size of the field. If I know X and Z, I ...
1
vote
1answer
528 views

primitive root of a very big prime number (Elgamal DS)

For encryption methods there is a need for (very large) prime numbers. So for Elgamal digital signature there is the problem of finding a primitive root of $(p)$ where $p$ must be very large prime ...
3
votes
1answer
136 views

Biased RSA moduli and ROCA

Say I can generate many 1024-bit RSA public keys $(N,e)$ with fixed public exponent $e = 65537$. They turn out to be heavily biased when computing $N \bmod x$ for small primes $x$. These congruences ...
3
votes
1answer
112 views

Malicious DH parameters without using composite numbers [duplicate]

I know that it's possible to generate DH parameters that lead to it being easy to attack (e.g. trivial composite numbers), but is it possible to create a malicious parameter that is not a composite ...
5
votes
1answer
89 views

Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?

Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$. Is it possible to determine in polynomial time ...
-1
votes
1answer
131 views

Integer Factorisation

If I have a set of numbers of the form $\{ {kp+r}:k\geq0\}$ with p a prime or product of primes k large in $\in Z^+$ and r fixed, is it computationally feasible to find a factorisation for any one ...
0
votes
1answer
75 views

generating prime p and q, with alpha of element of order q

I'm working on VSSS (Feldman) but I cannot understand the statement as follows: I'm not good in reading mathematical statements (but working on it). Can anyone explain this in simple mathematics. ...
1
vote
1answer
146 views

Linear Feedback shift register over integers

The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is: It is supposed to be a normal Linear Feedback shift register but it ...
2
votes
1answer
70 views

AugPake implementation Doubt K computation

try to implement the AugPake protocol in java using BigInteger. I am having some difficulty computing $K=Y^z \mod p$ because $z$ is always $0$, for $z={1\over x+(w*...
4
votes
2answers
209 views

Nothing Up My Sleeve Lim-Lee Primes

A few days ago I asked a question about the security of the Lim-Lee Prime Generation algorithm used by GNU Privacy Guard’s libgcrypt library. L. Carvalho provided a good answer to that question. ...
-3
votes
1answer
83 views

Are there stenography benefits to a “n-prime”?

As mentioned in this StackOverflow CodeGolf question, prime numbers can be redefined: One of my favorite definitions of the prime numbers goes as follows: 2 is the smallest prime. ...
3
votes
1answer
153 views

Safety of using GPG's libgcrypt prime generation for generating ephemeral Diffie-Hellman primes?

My company wants to generate new primes for every Diffie-Hellman key exchange. We are thinking of using the prime generation scheme in GPG’s libgcrypt library. The code documentation says that the ...
3
votes
1answer
277 views

Diffie Hellman unsafe prime vulnerability

I have done some research about how the DH key exchange is unsafe if an unsafe prime p is used (that is, $p-1$ has a lot of small factors). Many answers here on StackExchange claim that for any factor ...
1
vote
1answer
285 views

Is RSA vulnerable to possible PRNG + Miller Rabin test weaknesses?

Factoring a 2048 bit number is a difficult topic with a well known complexity. But it seems that p, q, the prime numbers used in RSA (order of magnitude: 10^308) are generated thanks to the ...
1
vote
0answers
258 views

See the RSA's $n = p q, e \text{ and } d$ from ssh-keygen

For learning purposes, how to get the RSA's parameters (I use standard notation): $n = p q $, where $p$ and $q$ are prime and $e$, $d$, such that $ed = 1 \ (mod\ \varphi (n)) $ when doing ...