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
0answers
43 views

Will a list of all prime numbers upto certain number of bits compromise crytopgraphic algorithms based on prime factorization? [duplicate]

I understand that many cryptographic algorithms depend on the difficulty of large prime factorization. Will a list of all prime numbers upto certain number of bits make it easy for an attacker to ...
4
votes
0answers
90 views

Source of very large prime numbers

The RSA cryptosystem makes use of $n=pq$ where $p, q$ are large prime numbers. With quantum computing, factorization might become easier, so it will probably be useful to use much much bigger $p$, $q$ ...
0
votes
0answers
24 views

RSA encryption. Does message have to be coprime to n? [duplicate]

If I understand correctly, for RSA to work we need the message(cleartext) M $\in Z_n$ and gcd(M,n)=1. That is M coprime to n. This is to fulfil the requirement for Eulers theorem. How does RSA make ...
3
votes
1answer
60 views

Repeated modular square roots to recover original base

I'm given a large prime $p$ and $c \equiv m^e \pmod p$, and $e = 2^{64}$. Typical RSA rules don't apply here, since $\phi(p) = p - 1$ is even, and $e$ is a power of two, so they share a common factor, ...
0
votes
1answer
90 views

why to use a safe-prime in Diffie-Hellman key exchange?

In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime. so my question is what extra benefit of using ...
8
votes
2answers
1k views

Is there a pseudo message that will encrypt and decrypt correctly if one of the primes is a pseudo prime in RSA

For prime number generation, one can use a probabilistic prime number generation algorithm like the Miller–Rabin primality test that will yield a composite as a probable prime with probability $\frac{...
3
votes
1answer
49 views

Proving that RSA encryption function with non-square free modulus is not a permutation

Here is a backgroung for the question on hand. While studying RSA I came up to the question about what happens if $p$ and $q$ involved in modulus computation are not actually primes? There is already ...
4
votes
1answer
91 views

Consequence of $p\bmod e=2$ in RSA prime generation

When generating a prime $p$ for use in an RSA modulus with public exponent $e$, it is necessary that $\gcd(p-1,e)=1$. When $e=3$, and since $p$ is a large prime, that implies $p\bmod e=2$. Assume an ...
0
votes
1answer
97 views

If $((p-1)*(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)*(q-1)) = 1$

If $((p-1)(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)(q-1)) = 1$. ($p,q$ are prime numbers ) Is this true, if yes why, if not why not ?
0
votes
1answer
55 views

ZKP for product of two primes

I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper. The proof is a 2 round where the verifier asks the prover to extract square roots of ...
3
votes
1answer
57 views

Computational trapdoor where the problem is tractable for both parties but easier for one

Usually the sort of trapdoors which are talked about are designed such as to make the computation intractable for one party and tractable for the other. But what if one party merely has a big ...
1
vote
1answer
61 views

With composite $n_1$ = $p_1q_1$, and a separate $n_2 = p_1q_2$, can the primes be calculated more efficiently than factorization?

Supposing that the (3 total) primes are kept secret? Does the reuse of $p_1$ allow an attacker to compromise $n_1$ and $n_2$ if the attacker guesses that both were generated with a shared prime ...
2
votes
1answer
121 views

How to produce large list of BigInteger prime numbers (RSA) in fast and efficient way

Hello fellow experts here, in order to use RSA to encrypt and decrypt in a controlled environment, we will actually need to have a list of prime numbers to do so instead of using library generated RSA ...
5
votes
2answers
149 views

Prime numbers of the form $(2^k)p+1$, for a given prime $p$

Let $p$ be a prime. (say 256 bit) Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such ...
2
votes
1answer
87 views

Problem with RSA deciphering

I don't quite get the algorithm yet. Sometimes it works and other times it doesn't,so clearly I am overseeing or misunderstanding something. I will just write what I did. My $N=143$ and has factors ...
3
votes
0answers
91 views

RSA calculate $d$ using Chinese Remainder Theorem with $d_p$, $d_q$ and $e$

Suppose for a RSA system I have the following variables given: modulus $n$, expononent $e$, $d_p$ and $d_q$Where, $d_p = d\bmod(p-1)$ and $d_q = d\bmod(q-1)$, Is it possible to find the private ...
0
votes
0answers
50 views

Trivariate Coppersmith Implementation

Bivariate Coppersmith is standard package in math software with number theory support. Bauer and Antoine Joux introduced trivariate Coppersmith in https://www.iacr.org/archive/eurocrypt2007/45150361/...
0
votes
1answer
96 views

Prime Factorization in RSA always leads to the product of two primes?

Lets prime factorize $30$: $$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$ We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two ...
0
votes
2answers
103 views

Why is Multiplicative group used in RSA or Euler's theorem but not additive?

I am on the verge to understanding RSA, but suddenly a question popped into mind. When we are calculating $U(N)$ i.e $U(PQ)$, we are taking invertible elements that are co-prime to $N$. For example, $...
0
votes
0answers
44 views

FLT is partly applying to RSA equation, and also relation between ED mod phi and Phi + 1 mod N

After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions. 1) We ...
2
votes
1answer
97 views

Relation between $N = P \times Q$, and $\Phi(N)$

When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem. I did understand how from invertible finite groups I ...
0
votes
1answer
74 views

Is it hard to find a big random easy to factor number?

Suppose that I give you the challenge of successfully factoring any very big random number. That is, you pick a big random number (say, 65536 bits) and try to factor it. If you manage to, you win. If ...
1
vote
1answer
136 views

Why is a prime number used in ECDSA?

So I need to write a piece for school about ECDSA and how it is secure. Now I thought I had a simple question, however, I can't seem to find an answer anywhere: Why does the p in the formula need to ...
0
votes
0answers
24 views

Three Pass Protocol Question!

Alice and Bob have agreed to use the Three Pass Protocol. p=1009 Alice chooses the encryption exponent e_A = 101 Bob chooses the encryption exponent e_B = 209 Now Alice and Bob send three ...
3
votes
1answer
239 views

Diffie-Hellman in Https: How are prime numbers picked?

I am trying to understand https, as I understand https uses the Diffie–Hellman method for keys exchange and then AES for encryption. But Diffie–Hellman needs two prime numbers, where do these come ...
0
votes
0answers
41 views

About the irreducible test for a polynomial over $GF(2^m)$ (its coefficients belong to $GF(2^m)$)

For the Miller-Rabin probabilistic primality test, we can apply it to test a big number whether a probably prime number or not. Does there exist a method to test a higher-degree polynomial over $GF(2^...
1
vote
0answers
37 views

How large a product out of 3 close-by factors need to be to avoid factorization?

For encryption a prime $P = 2 \cdot Q \cdot R \cdot S +1$ was used. An adversary want to solve the discrete log problem $m \equiv g^i \bmod P$. For this he want to use the Pholig-Hellmann algorithm. ...
7
votes
1answer
139 views

Distance between consecutive primes distribution

In several prime generation schemes I saw we pick a random number uniformly at random from a wide range and find the next prime after it. Obviously with such a scheme some primes are more likely than ...
3
votes
1answer
216 views

RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N?

For $N=pq$, if the first $x$ least significant bits of both $p$ and $q$ are leaked. what is the advantage in factoring $N$? Does this give an advantage beyond simply lowering the number of bits we ...
4
votes
0answers
50 views

Generalized Benaloh cryptosystem with $r=2$

Benaloh cryptosystem requires $\gcd(r, (q-1))=1$ which is impossible if $q>2$ (since it needs to be a large prime) and $r=2$. This confuses me, since Benaloh is referred to as an "extension" or "...
2
votes
1answer
61 views

Modification of RSA using two inverses, one for P mod (Q-1) and one for Q mode (P-1), instead of inverse d mod [(p-1)(q-1)], more or less secure?

Lets say I have the following modified RSA scheme We choose two large primes P, Q, with additional restriction that these are relatively prime to (p-1) and (q-1) We choose N = PQ as public key We ...
0
votes
1answer
69 views

Trial division + Miller-Rabin complexity

I was reading a paper that shows time complexity of Trial division + Miller-rabin test for creating prime number. T = N(T_rnd + T_td + T_mr) T_rnd denotes time for making rnd number, T_td denotes ...
0
votes
1answer
67 views

What does it mean for a number to be “in the order of” a prime number?

In some papers I'm looking at there is some language that says things like "Choose a random number in the order of prime q" and I see some syntax that it is referring to that looks s = Zq (where q is ...
3
votes
1answer
88 views

Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?

With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?
1
vote
1answer
70 views

Why do we use prime numbers apart from hard factorization?

Why are prime numbers important in cryptographic constructs? I am not interested in RSA examples where factorization is the hard problem itself, that makes sense. However wherever I go I encounter ...
0
votes
1answer
68 views

If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors?

Suppose you are given an algorithm $A$ which takes $y \in \{0, 1, \ldots , N − 1\}$ as input, and outputs $x \in \{0,1,\ldots,N − 1\}$ such that $x^2 \equiv y \pmod{N}$. Design an efficient, ...
0
votes
2answers
87 views

Would calculating the nth prime ruin encryption?

I'm sure there is some proof that the nth prime can be found. But if we knew, would encryption that relies on primes be easy to decrypt?
-1
votes
1answer
249 views

Factoring 2048 bit number is easy?

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? i used prime 95. and actually i am kinda curious how it found a factor so fast? i can even factor ...
1
vote
2answers
367 views

Efficient function/algorithm/method to do modular exponentiation

I was working on this project where I needed an RSA key, and I wondered if there was and more efficient way of doing $g^a \bmod n$ other than calculating $g^a$ and then finding the remainder when you ...
1
vote
1answer
60 views

Paillier Complex Residuosity problem?

Paillier Cryptosystem depends on both the factorization where $n = p.q$ and the complex residuosity problem which is defined in the original paper as: The problem of deciding n-th residuosity, i.e. ...
1
vote
0answers
47 views

Question about using residue number system for repeated multiplications

I understand that when you are using RNS you need a co-prime moduli-set e.g. ${\{m_1, m_2, m_3\}}$, and the dynamic range is the product of each modulus in that set $M = m_1.m_2.m_3$. Also it's ...
1
vote
0answers
57 views

RSA Modulus doesn't match the primes [closed]

I generated a 2048-bit RSA key with ssh-keygen. When running: openssl rsa -in key -noout -text The result is: ...
0
votes
1answer
76 views

What is a method for hiding RSA prime values from .exe De-Compiling?

I've just been looking into RSA encryption with C++ and am wanting to make a program that can en/decrypt files of my own custom file extension. Obviously I need to choose two primes numbers (for my p ...
-1
votes
1answer
49 views

Deterministic procedure for mapping an arbitrary value into a 𝑝,𝑞 pair for public key cryptography

I want public key cryptosystem to used for re-encryption as describe in Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal? Now i have little solution for ...
7
votes
1answer
411 views

Algorithm to find primes $q$ and $p$ with $q\, |\, p - 1$?

I understand that if $p$ is prime then $p-1$ must be composite (at least divisible by $2$ as it is even). But how does an algorithm find a prime $q$ such that $q \cdot r = p - 1$. I thought prime ...
3
votes
2answers
202 views

Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)?

Let $n = p*q$, with $p \neq q$ and $x^2=1 \pmod n$, $x+1 \neq 0 \pmod n, x-1 \neq 0 \pmod n$ (So x is a non-trivial square root mod n.) I don't see how $\gcd(x+1,n) \in \{p,q\}$ follows. I ...
-2
votes
1answer
161 views

Why can every prime number be written as 6k±1? [closed]

I want to know how to be sure that each prime number can be written in the form $6k±1$. How I can find the prime number that exists after a composite number with this property of prime or other ...
0
votes
0answers
18 views

In practice, do large prime generators account for difference in gaps between primes? [duplicate]

It is my understanding that a method for creating large primes is to: pick a random large number, check the number against trial division of a set of smaller prime numbers, check with something like ...
2
votes
1answer
418 views

Distribution of safe primes generated using different techniques

Is there any difference in the distribution of safe primes generated by creating prime $q$ and testing $2q+1$ for primality, compared to generating a larger prime $p$ and testing $(p-1)/2$ instead? ...
1
vote
1answer
581 views

How should I address message size limits in RSA encryption?

I am making an end-to-end encryption software program in Java using RSA. I am using BigIntegers and its number theory methods. (I know this is a very slow approach, but I just want to learn to the ...

1
2 3 4 5 6