New answers tagged rsa
2
votes
Is a prime shifting method for RSA modulus generation safe?
No it is not secure, at least for small amount of shifts.
Lets assume we applied $k$ bits circular shift to $p$ and obtained $q$. The relationship between $p$ and $q$ becomes:
$q = 2^{k}.p-m.2^{n} +m$....
- 558
1
vote
1-out-of-2 Oblivious Transfer with RSA
Yes, reductions modulo $N$ are missing in the question, for $m_0+k_0$, $m_1+k_1$ (even though they do nothing for the parameters used), and the final $17−22=−8$, which after reduction modulo $N=15$ ...
3
votes
RSA perfect square phi
Thank you so much @fgrieu for the detailed and understandable answer. I quickly implemented it in python for anyone else interested in this:
...
- 63
3
votes
Accepted
RSA perfect square phi
We restrict to RSA modulus $n=p\,q$ with $p$ and $q$ distinct primes, thus $\phi(n)=(p-1)(q-1)$.
For any given $(p,q)$ such that $\phi(n)$ is a square, there exists $(a,b,g)$ with $p=a^2g+1$, $q=b^2g+...
- 138k
2
votes
Cannot get RSA encrypt and decrypt to work in hardware and online calculator
The question says:
The way I am doing the encrypt and decrypt is breaking the message, exponent and modulus into 32 bit chunks and applying $(a^b)\bmod n$ to each chunk.
This fails because when we ...
- 138k
1
vote
Cannot get RSA encrypt and decrypt to work in hardware and online calculator
Any idea what I am doing wrong?
My initial inclination is that you might be interpreting the pem files incorrectly, that is:
Perhaps the value of the modulus is not what OpenSSL meant
Perhaps the ...
- 145k
4
votes
Accepted
In RFC 2313 (PKCS1/RSA) said you could recreate the Private key from 'n' and 'd', which later versions removed. Why?
There are probabilistic algorithms to factor $n$ into $p$ and $q$ from $n$, $e$, $d$. It's then easy to rebuild the full private key $(n,e,d,p,q,d_p,d_q,q_\text{inv})$. One such algorithm is there. A ...
- 138k
5
votes
In RFC 2313 (PKCS1/RSA) said you could recreate the Private key from 'n' and 'd', which later versions removed. Why?
2313 was obsoleted by RFC 2437. 2437 was obsoleted by 3447. 3447 might have been obsoleted by 8017 but does anyone use it?
The version history on PKCS#1 v2.2 reads:
Version 2.2 updates the list of ...
- 91.9k
0
votes
"crandall" - unsolved CTF challenge - ASIS-quals-2023
Actually still more information here.We know n can be written as n=(2^256x1+e1)(2^256x2+e2)(2^256x3+e3),by using some shifting skills we can get more about x1,x2,x3.For example we can easily get some ...
- 1
1
vote
Accepted
Possible to encrypt message without knowing recipient public key?
What about:
Bob publishes a public key for some secure signature system. Alice trusts it, or will get a way to trust it.
Bob draws a random secret 256-bit key $k$.
Bob symmetrically encrypts the ...
- 138k
2
votes
What happens if we know that for an RSA key pair, the equation $d^e \equiv c \pmod{n}$ holds?
As a complement to fgrieu's answer, here is an idea of the sort of issues that can occur.
Let's say that $d$ is taken as the inverse of $e$ mod $\varphi(n)$ (it would work pretty much the same with $\...
- 2,114
2
votes
Prove that if $e.d \equiv 1 \text{ mod } pq$ then it's impossible to have $e.d \equiv 1 \text{ mod } (p-1)(q-1)$
Now I want to prove that for the same pair $(e,d)$ it no longer holds that:
That you are running into difficulties proving it may be due to the fact that it is, as you have laid out, not true.
...
- 145k
4
votes
What happens if we know that for an RSA key pair, the equation $d^e \equiv c \pmod{n}$ holds?
Reformulating: it's asked if disclosing the integer $c=d^e\bmod n$ compromises the security of an otherwise secure RSA public key $(n,e)$ with private exponent $d$. I'll assume $0<d<n$, as ...
- 138k
0
votes
Chinese Remainder Theorem in a strange configuration
It is the same format. You can arrange the equations as $x^e \equiv c_i $ $mod$ $n_i $ by swapping sides, then you can apply Chinese Remainder Theorem to find the value of $x^e \equiv C $ $mod$ $n_1$$...
- 558
2
votes
Are Safe and Sophie Germain primes evenly distributed?
Recall that $p$ is a safe prime and $q$ is a Sophie Germain prime when $p=2q+1$ and both $p$ and $q$ are prime. Safe and Sophie Germain primes are sometime useful in cryptography, e.g. in variations ...
- 138k
2
votes
Are Safe and Sophie Germain primes evenly distributed?
So, as far as I can surmise, the existence of infinitely many Sophie Germain primes is still open. There is a preprint on vixra, see here [vixra is a kind of a free for all arxiv server] but it has ...
- 21.2k
2
votes
"crandall" - unsolved CTF challenge - ASIS-quals-2023
That sounds like a fun challenge. Let us look at what this code snippet is doing.
While it hasn't found a prime number p, it will go from $i = 512$ to $i = 256$ and ...
- 7,629
1
vote
How much can we compress RSA public keys with two equal size factors?
Marc Joye's method to achieve $2n/3$ prescribed bits is essentially a streamlined version of the following. Bernstein attributes this method to Coppersmith (2003), but it's not clear whether ...
- 12.4k
4
votes
Accepted
Is there an algebra group (or ring) in which computing the inverse element is hard without some trapdoor information?
Trapdoor groups with infeasible inversion have been considered in several papers since the Master's thesis of Hohenberger. They were considered a hypothetical assumption for a long time, but two ...
- 2,114
1
vote
Is gcd(e,p−1)=1=gcd(e,q−1) similar to gcd(e,phi(n))=1?
If $n=p\,q$, and $p$ and $q$ are prime, and $p\ne q$, then $\varphi(p\cdot q) = (p-1)(q-1)$, from which it follows that for any integer $e$, the propositions $\gcd(e,p-1)=1=\gcd(e,q-1)$ and $\gcd(e,\...
- 138k
Top 50 recent answers are included