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

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

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) = ...
user avatar
1 vote
1 answer
38 views

With RSA (n,d,e), can you guess the value of n, when it is not published; given some signed values: (V_i ^ e) % n

If you have an RSA keypair (n,d,e), and you don't publish n to the world, how many bits of security is that? For example, if I ...
user avatar
  • 319
0 votes
1 answer
43 views

How to break RSA when $q = e^{-1} \bmod p$?

This problem was posed during a recently ended contest. I am given a value for n and e. e = 65537. n is a 2048-bit number. p is a 1024-bit prime number. q is the modular inverse of e mod p. That's ...
user avatar
2 votes
0 answers
25 views

RSA small public exponent signature forgery - use part of the public key as cyphertext

I would like to ask you about what I think is a variation of BB'06 signature forgery¹. Unlike BB'06 where the forged signature is valid for any pkey with e=3 the one I have is valid only for one pkey. ...
user avatar
  • 21
-1 votes
0 answers
67 views

RSA tutorial question [duplicate]

Looking at the ASU.edu tutorial on RSA encryption, they use a strange notation: $$\text{Decoding exponent:}\quad d = e^{-1}\bmod(p-1)(q-1)$$ Normally when I see any number n taken to the -1 power, I ...
user avatar
  • 1
1 vote
1 answer
50 views

Signature check decrypts ciphertext

Can somebody lead me to existing literature on making the extraction of plaintext dependent on a valid signature check first? I didn't think it was possible to force signatures to be checked; but this ...
user avatar
  • 319
1 vote
0 answers
117 views

Are there any practical weaknesses in RSA where the private key is used to encrypt a message (signing), without padding? [duplicate]

I came across this scenario recently and would like to understand if there are any practical attacks against this implementation. An RSA private key is used to "encrypt" data. The public key ...
user avatar
1 vote
1 answer
44 views

Can asymmetric encryption be used in HMAC, and still ensure the data has not been tampered with? [closed]

Suppose I want to send a message, but not privately; I want everybody to see it, even an attacker in the middle. I would do this by appending a public key to the start of the data, which could be used ...
user avatar
  • 11
9 votes
1 answer
214 views

Does a 2047-bit factoring oracle affect 2048-bit RSA security?

I started wondering. RSA relies on prime factorisation being hard. So if a 2047-bit oracle machine existed that could instantly factor any 2047-bit number (and you can't look inside at how it works), ...
user avatar
  • 191
3 votes
1 answer
127 views

Is RSA-signing zero knowledge?

Is RSA-signing a given challenge $x$ a zero-knowledge proof of holding the RSA private key, for the modern definition of zero-knowledge proof (which I don't know!) Assume public and genuine RSA public ...
user avatar
  • 124k
-2 votes
1 answer
118 views

I have an idea how you could crack the keys in RSA

Hello everyone on the forum, I'd like to give you an idea of ​​how the keys in RSA could be cracked. I am a passionate amateur and I do not know if this idea makes sense, but I would like to present ...
user avatar
  • 1
1 vote
1 answer
51 views

In RSA, What does gcd(e,phi) != 1 means? Why always choose e = 2^n +1 not 2^n?

Recently I have few experiences with Questions in RSA which e is 2^n instead of 2^n+1, and that leads to gcd(e, phi) is not equal to 1... Won't this make the private key impossible to get? Is the ...
user avatar
  • 11
0 votes
1 answer
51 views

RSA question for public exponent is an even number but not 2, and not big

While Public exponent is an even number which means Can't get the d in normal way since gcd(e, phi) won't be 1, and in this case only used one prime number for N (multiple uses for one prime number) ...
user avatar
  • 11
1 vote
1 answer
94 views

If RSA uses $e$ with $\gcd(e,\phi(N))\ne1$ but $e$ is hard to factorize has an adversary still an advantage in finding $d$ for $m^{ed}\equiv m\mod N$?

Usually RSA uses an encryption exponent $e$ with $\gcd(e,\phi(N))=1$. This question shows why that need to be the case: For $\ne1$ there might exist no decryption exponent $d$ because other $m'\ne m$ ...
user avatar
  • 475
0 votes
1 answer
59 views

Prove the correctness of the RSA for $GCD(m_i,n)=1$ and $GCD(m_i,n) \neq1$ [closed]

How to make a proof of the correctness of the RSA encryption and decryption formula for $GCD(m_i,n)=1$ and $GCD(m_i,n) \neq1$ where encryption is defined as $c_i = m_{i}^e$ mod n and decryption $m_i =...
user avatar
0 votes
1 answer
100 views

What does Euler's theorem have to do with RSA?

In RSA we compute e (encryption key) and d (decryption key) $\bmod phi(n)$ and not $\bmod n$, so how come when we get the keys and encrypt and decrypt we use $\bmod n$ not $\bmod phi(n)$ using the ...
user avatar
  • 47
1 vote
0 answers
35 views

Implementation size of post quantum schemes

I was comparing classical schemes with post-quantum schemes. Therefore I was interested in the round three candidates of the NIST standardization process. So far I know, that those post-quantum ...
user avatar
  • 1,492
0 votes
0 answers
48 views

Does this encryption scheme have any major vulnerabilities?

Recently I asked a question of whether there is any cryptosystem that satisfies a number of properties (read the properties). Continuing to the promise I gave there, this is my attempt to construct it....
user avatar
  • 115
0 votes
1 answer
82 views

RSA Big prime picking [closed]

Is the random picking of big n-bits random numbers for primality test a time sensitive operation? If so, would an heuristic for limiting the search space (about 5-10x) without missing out on any prime ...
user avatar
  • 103
2 votes
1 answer
85 views

Is there a discrete log challenge?

RSA challenge is well-known and it has a wiki page. Is there a discrete log for $\mathbb F_p$ where $p$ is Sophie-Germain prime?
user avatar
1 vote
1 answer
69 views

Does Man-In-The-Middle attack isn't possible when we use reverse of RSA algorithm in Digital Signature?

We know that in RSA algorithm Sender A can send an encrypted message to receiver B without any prior exchange of secret keys. A just uses B's public key to encrypt the message and B decrypts it using ...
user avatar
0 votes
1 answer
94 views

RSA not encrypting properly when e=d?

I'm trying to implement the RSA algorithm with some random (valid as far as I know) generated values but for this combination, encryption/decryption doesn't work. ...
user avatar
  • 103
0 votes
2 answers
93 views

Isn't an asymmetric cipher (like RSA) algorithm sufficient for all basic needs, when speed is irrelevant?

Why I care: I want to implement some secure sessions for communicating over internet and since I am a complete amateur in this and don't want to spend a lot of time learning about cryptography or ...
user avatar
  • 115
1 vote
1 answer
40 views

Do RSA powers of two modulus always have MSB set to one and so when DER encoded have 0x00 prefix?

Looking at https://crypto.stackexchange.com/a/30616/16548 and all the ways I generate RSA keys (code, SSL) the MSB is always 1 and so when DER encoded has 0x00 ...
user avatar
  • 147
0 votes
1 answer
60 views

|RSA| Is it normal for $\phi(n)$ to work as RSA modulus?

So I was casually practicing RSA on paper for an exam, I did the whole process I wrote bellow, and when I tried the encryption and decryption I got distracted and instead of doing $m^e \mod n$ I did $...
user avatar
  • 1
0 votes
1 answer
63 views

Sharing RSA private keys using key exchange algorithms like Diffie–Hellman Algorithm?

Me and my friend would like to login to an SSH server using the same private RSA key. However, we don't want to transmit the key over the internet, for security. I am thinking if it's possible to ...
user avatar
0 votes
0 answers
36 views

How to securely implement a deadpool in a PoW blockchain?

Imagine you have a blockchain where the Proof of Work scheme is integer factorization. There is an opcode that takes two integers $N,M$ where it returns true if $M\not\in \{0,1,N\}$ and $N \mod M \...
user avatar
  • 21
0 votes
2 answers
57 views

Deducing a secret key from two different public keys

Show that if two different RSA public keys $p_k$s are known to an attacker for the same secret key $s_k$, then $s_k$ can be broken I've deduced that that if the 2 public key exponents are $e_1,e_2$ ...
user avatar
1 vote
1 answer
102 views

Would encrypting a message twice with RSA with different keys be more secure that once?

This was a practice problem for a class. The class is over now and I never solved it, so I thought I'd ask here. Let's ignored the fact that adding extra security to single textbook RSA is unnecessary....
user avatar
0 votes
0 answers
85 views

RSA: Obtain private key exploiting badly generated public key

I have to solve the following problem: What I have: $n$, a 2048 bit number What I need to find: $p$ and $q$ such that $n = p\cdot q$. What I know: With $p_1$ the first half of $p$ and $p_2$ the ...
user avatar
  • 1
0 votes
1 answer
68 views

Additively homomorphic (modified) RSA?

Is there a way to modify the RSA so that it's homomorphically additive? I did some research and came across a paper which describes MREA (Modified RSA Encryption Algorithm), an RSA modification that, ...
user avatar
0 votes
0 answers
48 views

Comparing the performance of ECC/RSA with post quantum protocols

I wanted to compare the performance of different cryptographic systems. There is a pretty good paper comparing the 3rd round finalists of the NIST competition. I was wondering if there are good ...
user avatar
  • 1,492
0 votes
1 answer
70 views

Proving that RSA CCA is possible

I'm reading from William Stalling's Cryptography & Network Security - 7th Edition To me the first line suggests $$(M^e\bmod n)\times(2^e\bmod n)=((2M)^e\bmod n)$$ which means that if we want to ...
user avatar
  • 103
2 votes
0 answers
62 views

Historical key sizes for RSA and discrete log [closed]

What is the historical pattern for key size increases for rsa vs discrete log? What are the current and future projected sizes for these?
user avatar
  • 882
0 votes
0 answers
42 views

recover private keys (RSA)generated with weak LCG

How is it possible to recover RSA private keys considering that weak LCG (random number generator) is used? I have some other keys (Public and private created with the same generator) and also some ...
user avatar
2 votes
0 answers
62 views

Bleichenbacher attack equation

In the Bleichenbacher attack, when the $|M_i−1| = 1$, we should choose $r_i >= 2(bs_{i-1} -2B)/n$ in order to increase the search performance. I don't quite understand how this $r_i$ value is ...
user avatar
  • 121
1 vote
1 answer
88 views

RSA Algorithm: What are the maximal possible locks that your friend can have so that he/she can secretly share that to you?

I found this question while preparing for exam. The question is Q)Suppose, you and your friends have a few numbers of locks and you all want to share that numbers among yourselves securely using RSA ...
user avatar
1 vote
3 answers
228 views

is RSA KTS-OAEP necessary? [duplicate]

Often data is encrypted using Symmetric Ciphers and Symmetric key is shared with recipient by encrypting it with recipient's Asymmetric Public Key. NIST Special Publication 800-56B, Revision 2 section ...
user avatar
  • 1,998
-1 votes
1 answer
87 views

Encryption of message concatenated with encrypted message

Is there a possibility to encrypt a message that is a concatenation of an encrypted message and another message ( encrypt_message + message )?
user avatar
0 votes
0 answers
91 views

RSA Hastad's broadcast attack with large numbers

I understand the theory behind Hastad's broadcast attack. Namely if we have three encrypted messages with the exponent e=3: ...
user avatar
  • 143
0 votes
1 answer
51 views

Is there a way to modify an existing RSA key pair so that the functionality remains?

I have an existing RSA key pair, how to 'derive' a different key pair based on the existing one so that the encryption decryption functionality remains but the original key isn't interchangeable with ...
user avatar
  • 3
4 votes
1 answer
79 views

Can you really ignore number of quantum processing steps needed for Shor's algorithm?

Answers to question RSA key length vs. Shor's algorithm suggest that e.g. 2048 bit RSA encryption would be trivially broken with 4099 qubit quantum computer using Shor's algorithm (best known ...
user avatar
0 votes
0 answers
35 views

RSA / AES issue : Decryption

I perform the following commands because I need to decrypt a file -encryption key file- (which is longer than module): cat key.enc | base64 -d > encryptedrawfile.txt openssl rsautl -decrypt -inkey ...
user avatar
  • 1
5 votes
2 answers
666 views

RSA Signing - Existential forgery and message prefix question. It's a weird one

I'm new to this. Please be kind. I have a theoretical question that I would like sanity checked: Bob and Alice are doing RSA signing without a hash function -- just putting a message in, and getting a ...
user avatar
1 vote
2 answers
74 views

Factorization of the product of two specific primes

Help me please. Consider specific primes $p = x^{d} + 1$ and $q = x^{e} + 1$ for some $x, d, e \in \mathbb{N}$. Can their product $n = pq$ be factorized faster than the product of general primes ? In ...
user avatar
1 vote
1 answer
63 views

Is there a general formula for the number of different sequences produced with $x\mapsto x^\alpha \mod N$?

Depending on $\alpha,N,x$ the sequence $x\mapsto x^\alpha \mod N$ can have a different length. If the first element $x_0$ is initialized with $x_0 = x_r^\alpha$ for a random $x_r$ the sequence will ...
user avatar
  • 475
1 vote
2 answers
776 views

What does "ECDHE_RSA" mean? [duplicate]

Hey i do have a question about cryptography: I know that Elliptic curve is cryptography algorithm and Diffie–Hellman is mechanism which is provide the two parties who wish to encrypt some data with a ...
user avatar
  • 11
2 votes
2 answers
179 views

Help with RSA CTF question

I'm trying to solve a CTF problem relating to RSA encryption. I can run a challenge binary that will read a flag from a file, the flag will match the following RegEx: ...
user avatar
6 votes
2 answers
537 views

RSA with exponent being a factor of modulus

This weekend I participated in a CTF, but came across a task that I wasn't able to solve. I can't find any write-ups so I hope you can help me. Given: $$ n = pq\\ c_1\cong m_1^{\hspace{.3em}p} \mod n\\...
user avatar
3 votes
1 answer
448 views

RSA decryption using CRT: How does it affect the complexity?

There is an efficient variant of the RSA using the CRT: \begin{align*} d_p &= d \pmod{p-1}\\ d_q &= d \pmod{p-1} \\ q_{\operatorname{inv}} &= q^{-1} \pmod{p} \end{align*} where the ...
user avatar
  • 133

1
2 3 4 5
51