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.
1
vote
2answers
237 views
Is there an algorithm for factoring N, which is just as simple as this one, but faster?
I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA.
It basically works like this:
You reverse the digits in ...
-2
votes
0answers
58 views
Patterns in primes, listing? [closed]
Is there a listing of all the patterns people have found in prime numbers? I think I have found a new one and want to check against what is out there to make sure.
Yes I know this sounds very very ...
6
votes
1answer
129 views
Solving hard problems in $\mathbb Z_{p}^{*}$ when $\mathbb p$ is close to $\mathbb 2^{n}$
Suppose, for some security parameter $n$ you choose a prime $p$ such that $p = 2^n+c$ for some relatively small $|c| < 2^m << 2^n$. I have seen such primes being called Pseudo-Mersenne Primes ...
10
votes
2answers
267 views
Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?
I take the definition of safe prime as: a prime $p$ is safe when $(p-1)/2$ is prime.
Safe primes of appropriate size are the standard choice for the modulus of cryptosystems related to the discrete ...
1
vote
1answer
110 views
How to calculate y value from ((y*y) mod prime) efficiently
i am working ECC-224 bit. can any one tell me, how to calculate y value from ((y*y) mod prime) efficiently for large bit numbers.
1
vote
1answer
33 views
Selecting a large NUMS Safe prime
Suppose I want to use the following simple hash function.
For a mesage $m$, take some public $a$ and prime $p$ and raise $a^m \bmod p$ (never mind the computational expense of this operation).
This ...
0
votes
1answer
54 views
Efficient algorithm for remainder calculation over prime field for ECC implementation?
I am working on 224-bit elliptic curve cryptography. In this 224-bit * 224-bit multiplication results 448-bit output. I am reducing 448-bit into prime field range( prime number $2^{224}-2^{96}+1$) ...
0
votes
1answer
46 views
Solving congruences using PARI
I'm having trouble finding info in the docs about how to solve a system of congruences. The closest I can find is 'matsolvemod' in here: ...
2
votes
1answer
94 views
Security of Pohlig-Hellman exponentation cipher?
I am looking into implementing Pohlig-Hellman exponentation cipher and I would like to know how secure that algorithm is? I am guessing it's security relates greatly to the prime number used in it. ...
0
votes
1answer
104 views
How to solve the reverse of an equation that uses MOD?
I've been tasked with reverse engineering an unknown crypto function. The function uses the following constants:
$a=380951$:
I noticed that this is a prime number
$b=3182$:
I noted that this is a ...
0
votes
1answer
118 views
ECDSA - point order criterion
i am creating some primitive demostration for ECDSA over small curve ( p < 229). But my implementation have some weird issues. Verify process return false even if the signature is correct. Because ...
5
votes
3answers
276 views
RSA primes vs. largest known primes
In the context of a new largest (mersenne) prime number being found this week -
The largest known prime number is now 2^57,885,161 − 1, and it took 5 years to find ...
2
votes
1answer
142 views
Visualization of cryptography
I think CrypTool is great software. And what I find most useful in it is visualization of algorithms such as Caesar, Vigenere, AES, DES. And my question is: does anyone know other tools which are ...
-1
votes
2answers
127 views
Is (2^333)-1 a prime number? [closed]
How can I see if $2^{333}-1 $ is a prime number?
Does this have to do with Mersenne prime numbers ($2^n-1$) ??
Thank you!
2
votes
1answer
105 views
Choosing good parameter for Lenstra's elliptic curve factorization
In Wikipedia, there is an article explaining Lenstra's factorization algorithm. As far as I got it, we choose some $e \in \mathbb{N}$ and a point $P$ on the curve and then calculate $eP$. While ...
2
votes
2answers
122 views
phi(P*Q) = (P-1) * (Q-1)
I was trying to understand RSA when I encountered the Euler Function. I do understand this: $\phi(P)$, where $P$ is a prime is $P-1$.
However it seems that for a number $N$ such at $N=P\cdot Q$ where ...
5
votes
1answer
278 views
Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme
Shamir's original paper (PDF, 197kb) describing a threshold secret sharing scheme states:
To make this claim more precise, we use modular arithmetic instead of
real arithmetic. The set of ...
17
votes
2answers
823 views
How are primes generated for RSA?
As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. ...
3
votes
1answer
108 views
Why does Schnorr's Digital Signature scheme necessitate two prime numbers?
One of the necessary components to the Schnorr Digital Signature scheme is a pair of prime numbers p and q such that q divides p-1. However, there is never a modular inverse taken of q so why is there ...
13
votes
4answers
545 views
Is Wiener's attack on RSA extendable to larger keys with low hamming weight?
Using small private exponents with RSA improves performance.
However, it has been shown (Wiener, 1990) that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the ...
1
vote
1answer
336 views
How can I use eulers totient and the chinese remainder theorem for modular exponentiation?
I'm trying to implement modular exponentiation in Java using Lagrange and the Chinese remainder theorem.
The example we've been given is:
Let $N = 55 = 5 · 11$ and suppose we want to compute ...
1
vote
1answer
497 views
ABC Conjecture's Impact on RSA Encryption
A recent proof of the ABC Conjecture has been released by one Shinichi Mochizuki. Now, I'm not well versed in mathematics but it would appear that this proof implies that finding prime factors could ...
5
votes
1answer
266 views
In layman's terms, how does Shor's algorithm work?
I've just been reading up on Shor's algorithm, and I find it both fascinating and baffling. I don't really understand much about it, other than that it can factor semiprimes in polynomial time.
Could ...
0
votes
1answer
219 views
What is the correct value for “certainty” in RSA key pair generation?
I'm creating an RSA key pair in Bouncy Castle and need to specify an int value for certainty. This Stack Overflow answer says it is a relative test for how prime the values are.
There is another ...
6
votes
1answer
564 views
Generating Random Primes
Although this has been extensively discussed around here, I'm curious whether my approach makes sense, or I should just stick to "the standard version".
I'm implementing some homomorphic encryption ...
1
vote
1answer
136 views
How are the primes used to generate RSA keys?
I am confused about how keys in RSA asymmetric encryption are generated and what the implications for open communications are. Textbooks say the one-way function is merely two primes (with some ...
4
votes
1answer
114 views
In RSA, rationale for prime $p$ with $p-1$ having prime factor $u$ with $u-1$ having large prime factor?
In the 1978 RSA paper, it is recommended, among other things, to choose primes $p$ such that $(p-1)$ has a large prime factor $u$. This was motivated by Pollard's p-1 algorithm. Further, the authors ...
3
votes
3answers
397 views
Is it safer to generate your own Diffie-Hellman primes or to use those defined in RFC 3526?
I was wondering if the prime numbers defined for use with Diffie-Hellman in RFC 3526 are more trustworthy than generating one's own, especially considering the recent Arjen Lenstra paper (Ron was ...
3
votes
1answer
572 views
How large should a Diffie-Hellman p be?
In a Diffie-Hellman exchange, the parties need to agree on a prime p and a base g in order to continue. Assuming some ...
2
votes
1answer
168 views
How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$
Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form?
This is actually a homework problem with a ...
4
votes
1answer
461 views
How to better generate large primes: sieving and then random picking or random picking and then checking?
I'm writing an RSA algorithm, and am wondering what is the best and/or usual way to choose the initial prime numbers (p and q).
I know of two methods to achieve this, one based on a prime number ...
6
votes
1answer
638 views
Why does the PKCS1 RSA private key structure contain more than just exponent and modulus?
The ASN.1 spec for the PKCS1 RSA private key format is as follows:
...
4
votes
1answer
180 views
How are trapdoor functions developed/found and where can I find existing ones?
Trapdoor functions are a fundamental part of public key cryptography. An example of the most common trapdoor is
Prime Factorization, used in cryptosystems such as RSA
How are these trapdoor ...
8
votes
3answers
372 views
Is it reasonable to assure that p-1 and q-1 aren't smooth?
I came across the requirement that, in RSA, $p-1$ and $q-1$ shouldn't be smooth, shouldn't consist of lots of small factors. Therefore my question:
How complicated is it to check whether $p-1$ is ...
3
votes
1answer
108 views
Is there a group of prime order which could fit the CT-Computational Diffie-Hellman assumption?
I'm trying to choose a group that is hard under the Chosen-Target Computational Diffie-Hellman assumption, according to the definition in this paper, in order to implement the oblivious transfer ...
8
votes
5answers
422 views
Is it feasible to build an index of prime factors?
Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing ...
5
votes
3answers
1k views
What place do prime numbers have in cryptography?
My understanding of hashing and encryption is rather limited. I certainly do not understand the mathematical formulas at play in these algorithms. With that said, what part do prime numbers play in ...
7
votes
3answers
3k views
How does one calculate a primitive root for Diffie-Hellman?
In the Diffie-Hellman key exchange, one of the steps involves calculating a primitive root of a prime number $p$. How would one go about doing so, considering that $p$ could be very large?
Is there ...
7
votes
2answers
482 views
Selecting a large random prime
Say I want a random 1024-bit prime $p$. The obviously-correct way to do this is select a random 1024-bit number and test its primality with the usual well-known tests.
But suppose instead that I do ...
21
votes
4answers
6k views
How can I generate large prime numbers for RSA?
What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption?
I'm aware that I can find any number of articles on the Internet that explain how ...
