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.

Filter by
Sorted by
Tagged with
0 votes
2 answers
75 views

Find the RSA private key only by knowing the public key, the ciphertext and that each letter in the alphabet was encrypted separately

Is there a way to determine the private key (or the phi value) without n factorisation if one knows the ciphertext and the public key and that each letter of the (English) alphabet has been encrypted ...
1 vote
1 answer
34 views

Create RSA Public/Private Keys with OID rsassaPss

I'd like to create a public/private RSA key pair where the OID of both keys is rsassaPss. I can create the private key fine but when I extract the public key I ...
0 votes
1 answer
22 views

Universal Dynamic Accumulators : all parties know keys p and q. Is the original set needed to validate set membership and non membership?

I read this paper on RSA cryptographic accumulators have some questions on a few points : "Universal Accumulators with Efficient Nonmembership Proofs" https://www.cs.purdue.edu/homes/ninghui/...
11 votes
2 answers
2k views

Validating an RSA public key

What kind of tests can be performed on a public key to check if it is likely a valid key? The tests should be relatively fast - i.e. not computationally intensive - and not include modular ...
  • 86.6k
0 votes
0 answers
57 views

How to perform an attack on similar messages?

Suppose I have two messages encrypted by RSA with the same public key (N, e), where: M1 = "Hello " + name1 + message M2 = "Hello " + name2 + message The names and the message is ...
1 vote
3 answers
83 views

Are the structures (groups/rings) that RSA operations are performed on actually R-modules?

Paolo, in Algebra: chapter 0, defines a left-$R$-module as a ring, $R$, an abelian group, $M$, and a map $(R \times M \rightarrow M)$ such that: $r(m+n) = rm+rn$ $(r+s)m = rm+sm$ $(rs)m = r(sm)$ $1m = ...
  • 151
0 votes
0 answers
35 views

Why does Batch RSA signature verification require messages to be different?

In Batch RSA signature verification with hashing, the setup is: Given $l$ different messages $m_1,\dots,m_l$: Signing: $\hat{S}=\Pi_{i=1}{^l}S_i \mod n$ where: $S_i = H(m)^d \mod n$ $ H:\mathbb{N} \to ...
  • 311
1 vote
0 answers
58 views

Power consumption of Post-Quantum Crypto vs. legacy crypto

Is there any educated views or references on how the PQC NIST finalists compare to legacy crypto with regards to power consumption? Many thanks
  • 323
2 votes
0 answers
279 views

In RSA, are e and d technically equivalent? [duplicate]

In the process of finding RSA key pairs, we first find a e that is relatively prime to φ(n) (where n = p × q), and then find d such that e × d mod φ(n) = 1. Is d also relatively prime to φ(n), or not ...
  • 147
0 votes
1 answer
73 views

Is it ok to create secret by signing known data (string) with RSA private key?

Imagine you have RSA key pair. You also have some text data. So public key and text data are visible to everyone. Question is, if you sign the text_data with the private key, is the result considered ...
  • 1
1 vote
0 answers
56 views

How to fix this zero-knowledge proof of knowing an RSA message?

I'm trying to come up with a Zero-Knowledge proof for the following setup. Using RSA encryption, Peggy chooses a random $M \in \mathbb{Z}^*_n$, computes $C=M^e \mod n$ and sends $C$ to Victor. Peggy ...
  • 311
1 vote
1 answer
55 views

Finding d of RSA given e and phi using SageMath

I am trying to find $d$ given $e$ and $\varphi(n)$. I found a solution online but I don't really understand why it works. ...
  • 11
0 votes
0 answers
64 views

Is there a special limit in the range of the hash function?

Is there a special limit in the range of the hash function? More specifically, is it possible that there is a cryptographic hash function that outputs c-membered subsets of the n-membered set? In ...
1 vote
1 answer
148 views

Solving system of equation based on RSA

I have got 4 variables $n$, $x$, $y$, and $z$: Here, $n = p\cdot q$ with $p$ and $q$ are distinct primes \begin{align} x &= m^p \bmod n\\ y &= m^q \bmod n\\ z &= m^n \bmod n\\ \end{align} ...
0 votes
2 answers
67 views

Learning RSA: decryption yields inconsistent result after modular arithmetic

I am still studying for my crypto 101 and I have a problem with one exercise that I can't find where I'm wrong... We have p=11 and ...
  • 115
0 votes
0 answers
75 views

Generate SHA256 fingerprint from RSA public key (string only)

I have the public key, the string itself (not a file), and I am trying to figure out the SHA256 fingerprint, as in the image attached. The default key generated by PuttyGen is SSH-2 RSA with a SHA256 ...
4 votes
2 answers
132 views

How to attest simultaneous knowledge of $2$ private keys?

I'm looking for a way for a single individual to sign or otherwise provide proof of ownership of two private keys from keypairs $A$ & $B$. Simultaneous ownership is important. Alice can't do part ...
0 votes
1 answer
187 views

Is there some restrictions on values of p,q,d,e etc in RSA algorithm while trying to encrypt English Ciphertext?

Background: I've seen that the value of plain text should be lesser than p*q as per this slide. I was reading Tanenbaum's Computer Network book the next night, and I saw this thing that I'm not sure ...
0 votes
0 answers
42 views

Semantically secure RSA with Multiplicative Homomorphism

Most real-world RSA implementations add padding and such that break the multiplicative homomorphism of raw RSA. However, this multiplicative homomorphism can be useful. I haven't seen any existing ...
  • 166
0 votes
1 answer
52 views

How to encrypt strings in RSA (exercise)

I'm trying to solve a crypto RSA problem from my last exam in a clean way, but I'm stuck in the last step... First of all, we are using an alphabet with 27 characters (i.e. spanish alphabet: A-Z + Ñ). ...
  • 115
0 votes
1 answer
96 views

How to find mod N in RSA algorithm given ciphertext and plaintext

I have a problem where I have to find mod N in a RSA cipher. I am given the following information: The public key (e) Plaintext (M) Cipher text (C) How can I reverse the equation C = (M^e) mod N to ...
1 vote
1 answer
57 views

RSA-based Double Ratchet Algorithm

I'm reading the Signal specification and they suggest to use EC keys, in particular with X25519 or X448 curves, both for the initial X3DH agreement and the DH ratchet. I've noticed that languages and ...
  • 113
0 votes
1 answer
56 views

Difference between DSA and RSA in terms of signature generation

For DSA, if the same message is signed multiple times on different occasions, the signatures will differ because the random value k is generated for each signature. This is not true of RSA signatures....
0 votes
0 answers
47 views

RSA / RS256 Encryption with the public key I have

safe to say I'm a complete beginner when it comes to cryptography... I believe the example output below is some sort of RSA (or RS256) encrypted string, and was just curious whether it'd be possible ...
  • 101
0 votes
2 answers
88 views

Is it possible to create digital signature with specific p, q, e values by using OpenSSL?

I'm trying to create the digital signature by using these parameters and RSA algorithm: p = 645353605880701501120167331073 q = 350784310265709643169455170929 e = 19 message = "G’day mate! As we ...
0 votes
3 answers
56 views

Do digital signatures without contextual information protect you against signed messages replay attacks?

Consider this scenario: A signs a message to B using A's private key. A then encrypts the signed message with B's public key. A sends both plaintext and encrypted message to B so that B can verify. ...
1 vote
0 answers
93 views

Breaking RSA with P,Q LSB bits using LLL Lattice reduction

This question is someway correlated to Breaking RSA with P,Q LSB bits but more specific. I would like to use LLL to fully reconstruct P,Q given some LSB bits of P and Q in an arbitrary base B. Let's ...
  • 31
2 votes
3 answers
158 views

RSA different ciphertext for the same plaintext

General My goal is to encrypt some strings and store them in a database. I am using RSA OAEP in Go (Golang): ...
1 vote
1 answer
229 views

RSA signature with restricted range of $d$

My question is: Alice signs messages using RSA with a public key $(e,N)$ and a private key $d$. Alice chooses $d$ in the range $N^{0.25} < d < N^{0.5}$. What is the time needed for Alice to ...
  • 11
2 votes
1 answer
174 views

Where is the definition of one-way trap-door function used in public key cryptography

This is a rather simple question but I've been unable to find a proper answer for this online. When defining an asymmetric (public key) algorithm is the one-way trap-door function usage referring to ...
2 votes
0 answers
57 views

Textbook RSA with $e=3$ and short random message

This is a simplified version of a question I made long ago, that never got an accepted answer. It's given $N$ of $n=2048$ bit, assumed hard to factor, which two prime factors each are $\equiv2\pmod3$, ...
  • 126k
0 votes
0 answers
74 views

RSA with huge ciphertext

I am trying to find the flag from an RSA ciphertext, I am able to get the factors from factordb.com but the given e is not ...
2 votes
1 answer
144 views

Breaking RSA with P,Q LSB bits

Let's say we have a certain amount of LSB bits of P and Q and we want to fully reconstruct them given N=P*Q. I know this problem was studied in literature by Coppersmith and that Lattice methods are ...
  • 31
1 vote
1 answer
63 views

How to break up plaintext for RSA?

Given a plaintext of length 20 over the latin alphabet {A, B, . . . , Z} and the RSA key (n, e) with n = 77. Find a way to break up the plaintext in as little as possible blocks of information, each ...
  • 143
0 votes
1 answer
88 views

How do we calculate a power with a gigantic exponent?

In RSA, signing the hash of a message is doing the operation $h^{d} \bmod N$ where $d$ is the private key. Given that the size of $d$ is usually 2048 bits and $h$ is a quite big number, the ...
1 vote
2 answers
91 views

Prove a plain text belongs to encrypted data

Given an encrypted (RSA) message and it's original plain text, is there a way to prove that the plain text belongs to the encrypted message ?
3 votes
1 answer
61 views

Bleichenbacher '06 signature forgery against modified PKCS1 v1.5 format

Bleichenbacher’s ’06 RSA signature forgery targets incorrect PKCS1 v1.5 implementations where padding checks are omitted and RSA keys with e = 3 are used. As per ...
2 votes
2 answers
535 views

How to select e for RSA test questions?

I know I am not supposed to ask for answers, which I am not. I have the solution but I don't understand how 'e' is selected, pls see my explanation below. I am doing practice questions for my Cyber ...
1 vote
1 answer
56 views

Are RSA keypairs proof of work?

My computer generates a 65536-bit RSA keypair in 106 minutes. Is there a way to generate them faster by some trade-off? Can they be created in bulk, so long as they're able to encrypt and decrypt? Is ...
  • 111
2 votes
0 answers
33 views

How to prove an RSA ciphertext matches a Paillier ciphertext?

Suppose I know an RSA public key $(n,e)$ and I create two ciphertexts: An RSA ciphertext $C_1 = m^e \mod n$ and a Paillier ciphertext $C_2 = g^m \cdot r^n \mod n^2$. Is there a known efficient method ...
  • 166
0 votes
1 answer
46 views

How is RSA-OAEP secure from CCA2?

Here the encryption is done as follows : $$C=P^e \textrm{mod} \, n =(P_1||P_2)^e \textrm{mod} \, n.$$ Here's my scenario that the adversary with CCA2 wins. The adversary chooses $X_1, X_2$ of the same ...
0 votes
0 answers
72 views

How do I decrypt an encrypted message with an RSA private key?

I have an encrypted password I must decrypt as part of a challenge. Along with the password came a few UNENCRYPTED RSA private keys From what I understand, all I need in order to decrypt the password ...
1 vote
1 answer
49 views

RSA: Does it worth to calculate missing CRT parameters when you have just N, E, D, P, Q?

OpenPGP defines RSA secret key in a way which differs from PKCS #1,having the aforementioned values plus U = P^-1 mod Q. However, OpenSSL seems to work only with <...
0 votes
0 answers
40 views

Encrypt user AES keys with AWS KMS RSA key

I am developing a web application in which each user has some part of his data that is stored encrypted. We are hosted on AWS and I want to use KMS as part of the solution. To not make the solution ...
1 vote
0 answers
31 views

How does Diogenes prove equivalence of discreet logs despite the candidates not being composed of safe primes

In the paper describing a protocol for distributed RSA modulus generation, Diogenes, "[they] employ a special-purpose $\Sigma$-protocol based on [Sho00] for proving correctness of exponentiations ...
  • 488
3 votes
2 answers
843 views

Is the Euler totient shared in the RSA algorithm?

For what I know from the RSA algorithm, the receiver of an encrpyted message needs the Euler totient to generate its private decryption key. If the sender has chosen two primes p and q, then the Euler ...
  • 139
2 votes
1 answer
33 views

How does the blinding become perfect in Ferguson's Randomized Blind Signature Scheme

Trying to figure out how the scheme works I came across the last paragraph of the page. As stated, for any possible additional factor we multiply by the specified power v of the element g. How did ...
  • 23
1 vote
0 answers
56 views

Additive Homomorphic Encryption scheme with very small ciphertext size

I'm looking for a Additive Homomorphic Encryption scheme which can allow a ciphertext of size smaller than 128 bit. I started studying this topic very recently so I don't have much knowledge, but I ...
0 votes
1 answer
96 views

Adversary calculating signature of $m$ given a signature over $m'$ for textbook RSA

Suppose $m$ is the message that the Eve attacker wants to sign with the RSA signature scheme with the public key $(n, e)$ and the private key $(n, d)$. Suppose the signer Eve is given oracle access to ...
  • 1
0 votes
0 answers
142 views

Find factors of N given RSA public key (e, N) and private key (d) [duplicate]

I am having some problems solving the following problem: find factors of N given RSA public key (e, N) = (11, 459703599527) and private key d = 125373708962. I calculated k = ed - 1/ N = 3, and Φ(n) = ...

1
2 3 4 5
52