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.

291 questions
Filter by
Sorted by
Tagged with
1answer
219 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 ...
1answer
445 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 ...
1answer
456 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 ...
0answers
616 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 ...
0answers
86 views

Probability of a prime factor [closed]

We are given an arbitrary number $n$ and a sequence of primes $p_1=2$, $p_2=3$, ..., $p_k$. I am interested in the following question: Are the events "Prime $p_i$ is a factor of $n$" independent for ...
1answer
157 views

For large prime P, how often is (P-1) evenly divisible by 65537?

When calculating prime numbers $p$ and $q$ for an RSA private key, one of the requirements is that $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, where $e$ is the RSA exponent (typically 65537). I'm curious ...
1answer
139 views

are all elements of ZpxZp in ECC definite over Zp

are all elements of ZpxZp in ECC (elliptic curve) definite over Zp ? otherwise: assume G a base point of ECC and n the order of G. why n is equal or nother to p*p ? (p a prime number). (Think to a ...
1answer
1k views

How to encrypt the number one using RSA?

for example: if we have public key : (5,221) and private key : (77,221) and we want to encrypt 1: c(m) = (m)^p mod n c(m)=(1)^77 mod 21 =1 so how to deal with ...
1answer
2k views

What algorithm does .NET use to generate primes for RSA and how can I verify it?

There is an implementation of RSA in C# .net, but how can people know that this implementation is considering all the secury stuff conserning to RSA? For example I want to know what is the algorithm ...
1answer
912 views

What are some of the best prime factorization algorithms and their effecitvity

I was wondering aren't the most used prime factorization algorithms a symbolic mile behind the security of the RSA cryptosystem? The way it looks to me is that every time an algorithm is able to ...
1answer
2k views

How to Check Strength of RSA Public Private Key

How to measure strength of RSA public private key pair. is it enough to only measure the length of primes used to generate N? how to check that primes p,q used to make N were selected truly randomly ...
1answer
191 views

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$?

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$, where $t$ and $p$ are large primes?
1answer
112 views

1answer
886 views

Find inverse in RSA

I've been reading on RSA for a while but there's something I still can't understand. When generating the key: once you find n = pq and φ(n), you choose a number d coprime with φ(n) and then you need ...
1answer
1k views

Mathematics behind end-to-end encryption

I am interested in end to end encryption, recently I read some articles on its principles but I can't find anything on the maths behind the encrypting and decrypting functions that relates private and ...
2answers
256 views

Can someone explain the definition of four square roots as it pertains to groups in Z*p?

So I'm given the following as a problem: When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $Z^∗_N$ have either zero or four square roots. A quarter of the points have four square ...
1answer
333 views

where does the prime number taken in DH algorithm in IPSEC

I am studying & configuring IPSEC ikev1 and in between i am analysing the wireshark captures. I am using the linux kernel for TCP/IP stack and user-space i took ipsec-tools. In the first two ...
2answers
542 views

Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p?

I have seen the NIST, SEC and Brainpool standards. They have used same prime for a particular bit curve (128,192,256,521). Is the prime value fixed for a particular security (field size)?
2answers
2k views

Why are elliptic curves constructed using prime fields and not composite fields?

I come across this: Numbers mod composite number does not form a field rather it forms a ring and every number has a multiplicative inverse under integer mod prime Maybe these are the reasons ...
1answer
384 views

Role of primitive roots in Pollard's P-1 factorization algorithm

I have recently been reading about different factorization algorithms and I came across this paper that discusses the Pollard's P-1 algorithm. In the footnote of the first page, it states... For ...
1answer
100 views

Proving additive inverse as generator of Z*p [closed]

Let there be $p\ ,q$ odd primes, such that $p=2q+1$. Let the be $a \in Z^*_p$ so that $a \not= \pm 1(mod\ p)$. Prove that if $a$ is not a generator of $Z^*_p$ then $-a$ is a generator of $Z^*_p$.
2answers
124 views

0answers
85 views

“Prime conspiracy”'s effect on cryptography [duplicate]

Recent news reported about the discovery of a "Prime Conspiracy" which can be read about here. In summary, researchers have discovered that the last digit of prime numbers have a greater ...