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,815
questions
2
votes
1
answer
75
views
RSA attack when size of $M^e$ and $N$ is close
Let say we have the following information:
$$ e = 3 $$
$C$ is the Cipher text and $M$ is the Plain text with $C=M^3\pmod N,$ and $N$ is a product of two primes.
and we have the size of the original ...
- 123
1
vote
1
answer
28
views
In the DGK Cryptosystem, how hard is it to recover g, if we have knowledge of the private key?
Given the knowledge of the values for $v_p$, $v_q$, $n$ and $u$, and knowing that $g^{u*v_p*v_q} \mod n = 1$, how hard is it to compute the value of $g$? My assumption is that it is as hard as the RSA ...
- 13
0
votes
0
answers
50
views
Coppersmith's Method when you know half of one of the RSA Semprimes [closed]
I have the following 300 digit semiprime
...
0
votes
0
answers
53
views
300 digits semiprime factorization with the first half of the factor known
Imagine this: there is a 300-digit semiprime, and you are given the first half of one of its prime factors (i.e., you are given the first 75 of 150 digits of that prime factor). Would you be able to ...
0
votes
1
answer
58
views
Encrypting AES-GCM Key with AES or RSA?
I am building an application with a hierarchy of key-sets (think encrypted messaging). Each key-set contains:
Symmetric (AES-GCM-256)
Asymmetric (RSA-OASEP-256)
Each key-set defines an encrypted &...
- 125
2
votes
1
answer
67
views
Security analysis of using RSA-OAEP and RSA-PSS with the same key
We all know that it is a bad idea to use the same key for multiple purposes. However it sometimes happens that non-cryptography-savvy people will make this mistake - specifically, that they'll use an ...
- 237
1
vote
1
answer
42
views
What is the difference between public and private RSA keys? [duplicate]
I have been learning about generating RSA keys and am wondering if there is a particular reason why the private key is the private key and the public the public. As far as I know the encryption is bi-...
- 11
0
votes
1
answer
66
views
Can an RSA 2048 public key be recovered from encrypted- and decrypted data?
I have a binary file and an encrypted file (.sgo). Can I get the public key from this data? The encryption used is RSA-2048.
1
vote
1
answer
86
views
What exactly is a VRF?
Random numbers are useful in many use cases such as blockchain. I know many blockchains or smart contracts employ VRF to generate "provably fair random numbers". But what exactly is a VRF?
I'...
- 111
2
votes
2
answers
481
views
Generating Carmichael numbers in polynomial time
I'm generating RSA 2048-bit keys with $p$ and $q$ of 1024-bit primes. For primality, I'm using the Miller-Rabin test. As Carmichael numbers pass the MR test, I tried to compute how many such numbers ...
- 475
1
vote
2
answers
82
views
How can I demonstrate the existence of such an isomorphism(look at the image below)?
While I was reading a paper from "Daniel Shumow" about recovering all possible plaintexts when bad RSA keys ($e$ and $\phi(N)$ aren't co-prime) generation occurs, I found this isomorphism (...
- 13
2
votes
1
answer
113
views
How to find N and e knowing that e = p and N = p*q?
I've been stuck in this problem for a while, this is a challenge about Symmetric RSA:
We know that
$N = p*q$
$e = p$
$ct = pt^p \bmod N$ (1)
We are given $ct$ (which is the flag encrypted) and 4 ...
- 43
2
votes
0
answers
55
views
0
votes
1
answer
62
views
Peculiar case of RSA
I am dealing with a case as follows:
P = 73, Q = 97.
N = 7081, phi(N) = 6912.
e = 7.
Now, to find decryption exponent 'd' we have to satisfy: (e * d) mod phi(N) = 1 - (i).
Aliter: d = e^(-1) mod phi(N)...
0
votes
0
answers
37
views
Is it really safe to exchange data without a handshake?
I want to be able to exchange data between personal devices within a local network via HTTP.
The point is that I want to use the same pair of personal asymmetric keys on both sides. It turns out that ...
2
votes
2
answers
117
views
Probability of Enhanced MR test outcome for NOT A POWER OF PRIME
I come up with an approach to find the probability of the outcome "PROVABLY COMPOSITE AND NOT A POWER OF A PRIME" of enhanced MR test.
In context of this question, the probability/error ...
- 475
1
vote
1
answer
66
views
Enhanced MR test understanding the steps in detail
I'm going through the Enhanced MR test cited in FIPS 186-5, I have couple of questions regarding the following steps
4.5 $z = b^m \pmod w.$
4.6 $\textrm{If }((z = 1)\textrm{ or }(z = w – 1)), \textrm{...
- 475
3
votes
1
answer
458
views
How wrong is NIST 800-89's Partial Public Key Validation for RSA step e?
NIST 800-89 Recommendation for Obtaining Assurances for Digital Signature Applications has recommendations for (Explicit) Partial Public Key Validation for RSA which include an example method. It's ...
- 144k
4
votes
1
answer
172
views
Enhanced Miller Rabin outcome for composite numbers
I'm going through the Enhanced MR test cited in FIPS 186-5, in which it is mentioned that a composite number can be COMPOSITE WITH FACTOR or COMPOSITE AND NOT A POWER OF A PRIME.
When I tested this ...
- 475
2
votes
1
answer
249
views
RSA like problem with unknown e and d
I have encountered a strange source code part in a soon-to-be-decommissioned legacy app, which uses an RSA-like scheme for "one-way hashing" data.
It works like this:
base^input mod N = hash
...
- 21
6
votes
1
answer
295
views
Find unknown primes from two RSA modulus
Suppose that $𝑝$, $𝑞$, and $𝑟$ are $512$-bit primes and for some integer $𝑎 < 10^5$, $𝑝 + 𝑎$ is also prime. We know the moduli $𝑛_1 = 𝑝 × 𝑞$ and $𝑛_2 = ...
- 557
0
votes
1
answer
84
views
Source code of generating private exponent for RSA?
I'm learning math of RSA. I'm interesting about realisation of computing private expoinent in source code.
Where can I read a well made implemenation? (I prefer Python or Go implementation)
I tried to ...
- 3
2
votes
1
answer
72
views
What Digital Signature Methods are Suitable for Microcontrollers?
Given the constraints in terms of processing power, memory, and energy, what digital signature schemes are commonly used and efficient for Microcontrollers? I have come across RSA with low public ...
1
vote
1
answer
188
views
Can the RSA public key be used for both encryption and decryption?
My understanding of RSA Cryptography is that the Public Key is used for data encryption and Private Key is used for data decryption. But on this website(https://www.devglan.com/online-tools/rsa-...
- 113
1
vote
1
answer
162
views
Weakness when encrypting using RSA private key?
I know that usually with RSA, you encrypt data using the public key, and decrypt using the private key. Or alternatively, you sign using the private key, and verify the signature using the public key.
...
- 13
2
votes
1
answer
89
views
Reduction from factoring to RSA and the Oracle RSA problem
Recently I read some papers related to RSA Brown16,AM09,BNPS01 and I learned that there is a variant problem of RSA is The oracle RSA problem (or one more RSA Problem) is $m+1$ copies of the classic ...
- 311
1
vote
0
answers
69
views
Does unlimited signing oracle leak the private key?
I am writing a PC software that uses a type of USB dongle as licensing key. The dongle functions as a signing oracle and does nothing more:
Given any message $M$, it first pads $M$ to $PadM$, then ...
- 111
0
votes
1
answer
124
views
RSA problem with unconventional calculation of phi
I have $\phi$,$N$ and ciphertext. But the $\phi$ is calculated with $\phi=(p+1)(q+1)$. I normally calculate $d$ but cannot recover the message.
1
vote
2
answers
344
views
P, Q, and G values in a public key
I came across a certificate that contains values $P,Q$, and $G$ besides the public key.
Obviously, $P$ and $Q$ here are primes, but not the two secret primes. I am curious are those values
...
- 113
0
votes
0
answers
92
views
rsa special private key attack
This is a level 3 challenge in Mystery Twister.
https://mysterytwister.org/media/challenges/add/mtc3-kitrub-04-speciald-paramter.txt
https://mysterytwister.org/media/challenges/pdf/mtc3-kitrub-04-...
- 1
-1
votes
1
answer
124
views
1
vote
1
answer
86
views
Shannon's Perfect Security for Asymmetric Encryption
I have the following definition of Shannon's Perfect Security.
Assuming messages and keys are drawn randomly from some distribution then:
The probability of guessing plaintext m is not enhanced by ...
- 75
6
votes
3
answers
4k
views
Why does it take longer to generate suitably large primes for Diffie-Hellman key exchange as opposed to for RSA encryption / decryption?
For RSA, we need two primes p and q to define N = pq. We will only look how long it takes to generate a prime for p because the process is similar for q.
From my lecture slides, my professor states ...
- 63
1
vote
1
answer
31
views
What is the best possible security for authentication of entity?
The classical security for authentication is computational provided by RSA or EC based signatures. With the advent of new PQ schemes the security claims are upgraded though nothing is proved. So the ...
- 171
1
vote
1
answer
83
views
Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?
SUBEXP is defined as the intersection of DTIME(2^n^c) over all c>0. The order of the Quadratic Sieve algorithm is O(exp((k+o(1))(logN)^1/2(loglogN)^1/2)). Doesn't this imply that the decision ...
- 13
0
votes
0
answers
74
views
Reaching the bound of Boneh and Durfee Attack
According to the paper, theoretically,we can get $\delta=0.292 \lt 1-\frac{1}{\sqrt{2}}$,but how to set the lattice and implement it in sagemath? I generated some data
by
...
- 1
2
votes
1
answer
149
views
Confused about use of Euler totient function in RSA
I'm reading a book and I arrived at the part that explains 'textbook' RSA. It explains that given a modulus $n=pq$ and public exponent $e$ that we can encrypt $x \in \mathbb{Z}^{*}_n$ by setting $y=x^...
- 129
0
votes
0
answers
37
views
Sending public key trough untrusted server
I am developing end-to-end encrypted chat system (which is open-source). When I want to give other client my public key, I need to send it trough server, right? I want to make sure no one can edit the ...
- 1
3
votes
3
answers
722
views
Why is 65537 always coprime to φ(N) in RSA?
Implementation of the RSA cryptosystem often uses the number $65537$ as a public exponent. It is a requirement that such numbers have an inverse modulo $\varphi(N)$, where $N$ is usually a product of ...
- 165
1
vote
0
answers
137
views
Random padding of RSA-signed message at end instead of beginning of the message
I’ve a signature scheme for 1024‒bit RSA with a 65537 exponent. The signed message is constructed as follows:
760‒Bits fully_user_controlled_message_content+8 Bits incremental nonce+sha256(...
- 240
1
vote
0
answers
99
views
Break RSA knowing N, e, dp+dq
In a cryptography exercise, I have to factor $N$ only knowing $e$ and $d_p+d_q$ (not $d_p$ and $d_q$ separately).
I came up with the following equations:
$$e*(d_p+d_q) = 2+K_p(p-1)+K_q(q-1)$$
$$e*d_p \...
- 11
0
votes
0
answers
651
views
RSA decrypt using Openssl error : Public Key operation error
Hello im got stuck at ctf crypto challenge, so at the challenge is given 3 file which is
flag.enc pub.key priv.key
,
so i tried to decrypt using openssl here is ...
- 1
0
votes
2
answers
96
views
Public proven methods to generate SSH key from pass phrase?
Do we have something proven APPS for generate ssh key from some words?
I mean private key(without reason wich type rsa or eleptic curves) generated deterministic from seed
I found this fork of ssh-...
- 3
2
votes
3
answers
168
views
How often do hard-to-factor numbers occur?
[Computer scientist here who is not totally familiar with the factoring literature -- please forgive my ignorance.]
It's well known that hard-to-factor integers, $n$, are typically semi-primes, such ...
- 121
0
votes
1
answer
125
views
Deriving the RSA private key [duplicate]
Is there any way to derive the RSA private key from another RSA private key?
Let's say I have a base RSA key $(P, Q)$ (both prime), and then use some salt and an algorithm that creates a new primes, e....
- 3
4
votes
1
answer
341
views
How can I understand the gap between CPA and CCA1?
I have read lots of books about CPA,CCA1,CCA2. I understand how to get an example satisfies CPA but not CCA2. However, I can't find such a scheme which is CPA but not CCA1. What is the extra advantage ...
0
votes
0
answers
82
views
What is insecure about adding salt to your plaintext before using RSA? [duplicate]
RSA can't be used securely as is as it is deterministic. So an encrypted "yes" always looks the same. A simple workaround, which is apparently not secure, is to add 100 bits, say, of random ...
- 299
2
votes
2
answers
1k
views
How do RSA implementations avoid cases where the ciphertext and N are not coprime?
I'm trying to better understand RSA. One attack I've read about is when the encrypted message $y$ and $N = p\cdot q$ share a common factor. If this happens, we can easily factor $N$ to obtain $p$ and $...
- 123
1
vote
2
answers
1k
views
sign a JWT with RS256 using a RSA-PSS SHA256 key pair?
Given a private key using algorithm RSA-PSS with SHA256 is it possible to use this key to sign a JWT using algorith RS256 (RSA with SHA256) instead of PS256 (RSA-PSS with SHA256)?
The German ...
- 113
0
votes
1
answer
220
views
Prove RSA scheme is insecure [closed]
Im reviewing my crypto and I would like to prove the following: RSA experiment where the adversary is given N, e, and y. The adversary knows p, q.
I know the RSA scheme is built on the idea that it is ...
- 101