Questions tagged [rsa]
An asymmetric (e.g. public-key) cryptosystem, based on modular exponentiation with big exponents and modulus. RSA can be used both for signature and encryption with proper paddings.
2,740
questions
0
votes
0
answers
7
views
Possible to encrypt message without knowing recipient public key?
Assume Bob is sender and Alice is future recipient.
In ideal situation Bob know Alice public key, and encrypt message with it.
But what if Bob don't know Alice public key (he only will know Alice ...
- 1
-3
votes
0
answers
30
views
Factoring RSA $N = pq$ knowing that $(p+q) >> 200$ [closed]
We have $N = pq$, with $p$ and $q$ are prime numbers, and $hint = (p + q) >> 200$. How to find $p$ and $q$?
0
votes
1
answer
24
views
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)$
I am studying RSA cryptosystem and here is the question that came to my mind. Let's pick $p, q$ to be two primes and $n = p * q$. From that we calculate Euler's totient function:
$$
\phi(n) = (p - 1)(...
2
votes
2
answers
57
views
What happens if we know that for an RSA key pair, the equation $d^e \equiv c \pmod{n}$ holds?
If we possess the knowledge that the expression $d^e \equiv c \pmod{n}$ holds for an RSA key pair, what would be the implication or consequence of this? Here, $e$, $n$, and $d$ represent the public ...
- 487
0
votes
1
answer
55
views
Chinese Remainder Theorem in a strange configuration
Normally, the chinese theorem looks like this:$$
x = a_1 \bmod n_1\\
x = a_2 \bmod n_2\\
x = a_3 \bmod n_3$$
but what to do if in my situation it looks like this:$$
c_1 = x^e \bmod n_1\\
c_2 = x^e \...
- 1
0
votes
2
answers
219
views
Are Safe and Sophie Germain primes evenly distributed?
Do Safe and Sophie Germain primes maintain a relatively stable distribution as numbers get larger, or do they become rarified beyond a predictable value?
This is important in one area of triangular ...
3
votes
1
answer
128
views
0
votes
0
answers
79
views
Textbook RSA on random numbers mod a smaller prime
I have a protocol where I have a random one-time number message $m \in \mathbb{Z}_p$, where $p$ is a 256 bit prime from an Elliptic Curve (EDIT: The order of an elliptic curve prime order group). I ...
- 313
2
votes
1
answer
227
views
Is there an algebra group (or ring) in which computing the inverse element is hard without some trapdoor information?
Specifically, I want an algebra group $G$ (or ring $R$) features:
Given elements $g,h\in G$ (or $R$ ), computing $g\cdot h \in G$ (or $R$ ) is easy.
Given an element $g \in G$ (or $R$ ), finding the ...
- 368
0
votes
0
answers
83
views
How to create RSASSA-PSS keys using openssl?
I am trying to understand the RSASSA-PSS and process of generating keys with rsassaPss. I am using below ...
- 109
0
votes
0
answers
40
views
How to find modulus and decrypt a message with a CPA on textbook RSA. The encryption oracle only allows two queries
The encryption oracle only allows you to encrypt a custom message $m$ or the secret message $m_s$. In both cases it asks you to choose a public exponent $e>16$. Of course, $n$, is not available.
If ...
0
votes
0
answers
82
views
Decrypt RSA knowing N, invp, and invq
im having a problem while solving a RSA problem, so i have python script to create a RSA key and cipher, from that i have n, invp, and invq. so my question is possible to decrypt the message only with ...
- 1
1
vote
1
answer
78
views
Is gcd(e,p−1)=1=gcd(e,q−1) similar to gcd(e,phi(n))=1?
I wonder, is $\gcd(e,p−1)=1=\gcd(e,q−1)$ similar to $\gcd(e,\phi(n))=1$ ??
- 11
3
votes
1
answer
217
views
RSA/ ECC keygen HW vs SW
i have a pretty straightforward question but i can’t seem to find an answer :
Regardless of the physical protection provided by an HSM or TPM or any hardware cryptographic key storage system, are keys ...
- 51
0
votes
0
answers
46
views
In RSA Encryption, Can I choose the public exponent e > m (modulus) ? or e > φ(n)? [duplicate]
In RSA ,the encryption, Can we choose the public exponent (e) greater than m (modulus) or e > φ(n) ? I wonder about choosing public key exponents (e) because the most information on the internet or ...
- 11
3
votes
1
answer
91
views
How much can we compress RSA public keys with two equal size factors?
Can we define an RSA variant in which the public key with $n$-bit public modulus $N$ has a compact representation of $\kappa\ll n/2$ bits, with a security argument that it is as safe as regular RSA ...
- 138k
4
votes
1
answer
149
views
Is this new bound for Wiener Attack well accepted?
I found this recent paper The Wiener Attack on RSA Revisited:
A Quest for the Exact Bound, which reported a new bound $d\le \frac 1 {\sqrt[4]{18}} N^\frac 1 4$. Is this well accepted in the ...
- 159
0
votes
0
answers
47
views
In RSA Encryption, Can the public exponent e > m (modulus) ? and can we choose any public key without paying attention to the conditions? [duplicate]
In RSA ,the encryption, Can we choose the public exponent (e) greater than m (modulus) or e > φ(n) ?
I wonder about choosing public key exponents (e) because the most information on the internet or ...
- 11
10
votes
5
answers
2k
views
Best cryptographic algo with asymmetric cost: expensive to sign, cheap to validate
I'm looking to prevent a DDoS attack on a web service, by making the cost of performing an attack prohibitive. Typical users will only need to call out it once a day, and can afford to spend a few CPU ...
- 203
1
vote
1
answer
159
views
Cryptography to tackle deepfake, proving the photo is original
Deepfake technology has become very difficult to tackle due to sophisticated machine learning algorithms. Now, even when a journalist or bystander provides photo or video evidence, the culprit denies ...
- 111
0
votes
0
answers
33
views
RSA derivation of ed=1 mod(ϕ(n)) [duplicate]
I know that $m =m^{ed} \bmod n$, and there is Euler's $a^{\varphi(n)} = 1 \bmod n$, but how do we derive that $ed=1 \bmod(\varphi(n))$ holds for all m. Where does that equality come from? Couldn't ...
- 1
0
votes
2
answers
377
views
Best cryptographic method to distribute license files
I will describe my problem high-level, and not ask a very specific cryptographic question, since I am open for general suggestions as well. So in my question I will only speak about "security ...
- 111
0
votes
2
answers
71
views
Is signature same as hash value encrypted with the private key in openssl?
Computing the signature of hello.txt file which has the text hello in it, here is done in two steps:
...
1
vote
0
answers
93
views
Is there any harm using a pseudo-prime endorsed by a probablistic test like Miller-Rabin in RSA?
In RSA, the decryption exponent $d$ is typically calculated as $$d= e^{-1} \bmod{(p-1)(q-1)}$$ or $$d = e^{-1} \bmod \operatorname{lcm}{(p-1, q-1)}$$
where $p$ and $q$ are often randomly selected ...
- 9,001
2
votes
1
answer
119
views
Operands size in RSA Cryptography (C language)
I am trying to implement the RSA cryptography algorithm using C language. I am not sure of the size that each operand should have. Let me explain:
RSA requires to generate two huge prime numbers p and ...
- 123
1
vote
0
answers
18
views
Curious behavior of EVP_DigestSign for DKIM
Difficulties porting code to OpenSSL 3 may raise some doubts on digest signing. Before version 3 came, digest signing was the only way to use ED25519. On version 3, RSA_sign() being deprecated, I ...
- 111
0
votes
1
answer
178
views
RSA - Twin Primes across two messages
This was a CTF challenge I was unable to solve, but I thought I may had come close.
We were given two $N$'s $N_1$ and $N_2$ each calculated with $P_1 \times Q_1$ and $P_2 \times Q_2$; however, $P_1 = ...
- 1
0
votes
0
answers
49
views
RSA random key generation [duplicate]
How RSA keys are tested for primality if they are random generated? I imagine this could be time consuming task.
1
vote
1
answer
125
views
RSA signature with random padding
I used to think that adding random padding to an rsa plaintext was to prevent attack when you can ask/have access to different ciphered output, and decipher it without access to the private key (under ...
- 11
3
votes
2
answers
205
views
Textbook RSA using multiple low public exponent e
I'm working on finding an attack on textbook RSA using non-prime, low public exponents $e_1,e_2$ for each encryption.
Given $$c_1 = m^{e_1}\space mod \space n \\ c_2 = m^{e_2} \space mod \space n$$
I ...
- 41
0
votes
0
answers
84
views
RSA encryption two characters at a time
I have a question in regards to a task I've been given at uni. I need to encode the string 'Cyber' 2 characters at a time with RSA with padding being space.
What do ...
-1
votes
2
answers
128
views
Encrypt with private key decrypt with public key
I want to sign and transmit a short message, which contains a few simple hashes. My objective is not to prevent an attacker from inserting a fake message, but to ensure that the attacker cannot define ...
- 99
0
votes
1
answer
73
views
Trying to understand the basic principle of RSA from Wikipedia
Quote from https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation
A basic principle behind RSA is the observation that it is practical
to find three very large positive integers $e$, $d$, and $n$,...
- 103
1
vote
1
answer
247
views
A RSA crypto CTF chanllenge with known private key ,cipher text and modules factor n
Here is a CTF chanllege about RSA(The competition has ended for serval hours),and here is the critical encryption code:
...
- 23
1
vote
1
answer
108
views
RSA: in $E(x) \equiv x^e \pmod N$, do we apply the mod function to $x^e$?
When one is computing $E(x) \equiv x^e \pmod N$ (where $N = pq$) in RSA, what is the precedent for which number in the residue class of $x^e$ to have as the result of this computation? Does this mean ...
- 123
2
votes
1
answer
113
views
How secure is this modified RSA (SRA / Mental Poker) algorithm?
I'm making a peer-to-peer game client using an already existing protocol where messages are broadcasted to all people on the network, and messages are already proven to be from a given user. One of ...
1
vote
2
answers
64
views
RSA: does it matter that we recover something congruent to x rather than equal to it?
In the proof that RSA successfully decrypts the message $x$, we show that $x^{e^{d}}\equiv x \pmod N$. However, I am wondering whether it is a problem that we don't recover $x$ exactly, but merely a ...
- 123
0
votes
0
answers
49
views
JSON Web Encryption (JWE) Key Wrapping Fundamentals - How To Encrypt Content Encryption Key?
The JSON Web Encryption RFC 7516 says:
Encrypt the CEK with the recipient's public key using the
RSAES-PKCS1-v1_5 [or RSAES-OAEP] algorithm to produce the JWE
Encrypted Key.
Assuming a client/server ...
- 101
0
votes
0
answers
40
views
Implementation of Ring Signature
I have implemented a ring signature in a Python program, To keep it simple, I have Alice and Bob. Based on this ring equation:
$$ v = E_k(y_s⊕E_k(y_i⊕v))$$
I will get:
$$ y_s = E_k^{-1}(v)⊕E_k(y_i⊕v) \...
- 11
0
votes
1
answer
275
views
RSA Oracle - CTF
I am trying to solve a challenge regarding a RSA oracle which allows me to encrypt/decrypt any plaintext/ciphertext I want, but there are a few checks that I have to bypass, and my goal is to decrypt ...
- 145
4
votes
2
answers
449
views
Why does OpenSSL RSA signing process need the public exponent?
I am trying to fully separate RSA key pairs by breaking down $(N,e)$ for public part and $(N,d)$ for private part. From my understanding of RSA signature process, the message to be signed is digested ...
- 43
1
vote
0
answers
58
views
Integer factorization $n = pq$ with additional knowledge of $\lfloor \sqrt{p} \rfloor \oplus \lfloor \sqrt{q}\rfloor$
We know that we can factor integer $n = pq$ when we know that $p\oplus q$, where $\oplus$ means xor. If we know $\lfloor \sqrt{p} \rfloor \oplus \lfloor \sqrt{q}\rfloor$, can we factor $n$?
- 11
0
votes
0
answers
40
views
RSA with p and q being generated by pow expression of weak random seed
n, e and modulus of RSA are given and n is very large. p and q are primes generated by pow(7, random_seed, modulus), and the seed that p and q used is very close. ...
- 1
3
votes
1
answer
537
views
How brittle is the current public key encryption infrastructure
Edit: One half of the answer to this question also applies to a recently asked and now deleted question regarding the impact of an algorithm which breaks DLP over integers but has no impact on ...
- 21.2k
1
vote
1
answer
103
views
finding r-th root in $\mathbb{Z}/n\mathbb{Z}$
I was reading the paper One-way Accumulators: A Decentralized Alternative to Digital Signatures by Benaloh and de Mare [link], and in section 4.2, they say that given $z\in (\mathbb{Z}/n\mathbb{Z})^*$ ...
- 445
2
votes
1
answer
99
views
Prove with ZKP that I have encrypted a message $v + random\_number\cdot c$ given an RSA public key?
I want to create an application in which users can cast vote to blockchain in encrypted form using RSA. The private key will be revealed only after completion of the election.
My major use case is as ...
- 71
0
votes
0
answers
85
views
Question regarding JWK generation using RSA-PSS 4096
Summarized Question:
In the context of JWK generation using RSA-PSS 4096bit with SHA-256, where the public exponent is "e" = 65537, is there any situation ...
- 1
0
votes
0
answers
42
views
Transportation Key (KEK)
I was studying about how to transport keys from one HSM environment to another and it came to me that I would need some sort of transportation key so the HSM keys would be double encrypted.
How would ...
- 101
1
vote
1
answer
313
views
Is this proof of RSA's correctness sufficient?
In a lecture at my university, the following proof of correctness of RSA is given (the lecture is not mainly on cryptography or even computer science):
$m^{ed} \equiv m^{ee^{-1}} \equiv m^{1} \equiv m ...
- 113
0
votes
0
answers
30
views
Cryptographic Applications of Composite Modular Exponentiation
I've developed an algorithm for fast modular exponentiation modulo composite numbers with known factorization. I'm not very well versed in cryptography, so I'm wondering if any of you know of an ...
- 113