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.

learn more… | top users | synonyms

3
votes
2answers
166 views

Using single EC cert/keying material to derive symmetric encryption key (for storage)?

The situation involves a single party (single certificate) who would want to AES encrypt a file that they can later decrypt. Assume the EC certificate + EC keys have a purpose i.e. "File encryption" ...
3
votes
0answers
144 views

Ring Signature - paper/code difference in trying to solve inverse trap door function?

there is a paper on ring signatures and a python implementation of it here. The Step 4 in the paper describes $y_s = v =C_k,_v(y_1, y_2, ... y_r)$ for all $1 \leq i \leq r$ where $i \neq s$. The ...
3
votes
0answers
203 views

RSA reencryption scheme

Is there such an algorithm that would allow to upgrade the encryption of a RSA-encrypted message without revealing the plaintext to the untrusted user? Basically, such an algorithm would probably be ...
2
votes
2answers
226 views

P = NP and current cryptographic systems

I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems. My ...
2
votes
2answers
158 views

Is it safe to use RSA as a proof-of-work system?

Suppose I devised the following challenge-response proof-of-work system: A server generates a 2048-bit RSA modulus, and uses the "public" exponent (usually 65537) to sign a random nonce a fixed ...
2
votes
3answers
986 views

Is 512-bit RSA still safe for signature generation?

The standard CSP on Windows XP only supports RSA up to 512-bit, which means that it's the maximum key size I can use for authenticity verification of updates. The public key is embedded in the ...
2
votes
2answers
437 views

How exactly are GPG keys mathematically related, and prime numbers inside of GPG general

Before anyone suggest it, I've yet to pick up "Applied Cryptography" I'm planning on picking it up the next time I visit amazon. I know that the keys are somehow mathematically related, and I know ...
2
votes
3answers
289 views

RSA assumption and cryptography

The RSA assumption states that it is hard to find $m$, given $c = m^e \bmod{n}$, $e$, and $n$ (for appropriate choice of $n,e$). Suppose that there exists an algorithm, $D(c,e,n)$, that finds $m$ in ...
2
votes
2answers
194 views

How does this happen in RSA malleability?

I don't understand how the $E(m)$ turns into $E(mt)$. I mean, I don't know how does that transformation happen and how does the equation occur. $$E(m) \cdot t^e \bmod n = (mt)^e \bmod n = E(mt)$$ ...
2
votes
2answers
1k views

Is RSASSA-PKCS1-v1_5 a good signature scheme for new systems?

Is RSASSA-PKCS1-v1_5 a good signature scheme to recommend that people use in new systems? Is it believed to be secure and represent the state-of-the-art in RSA-based signatures? I understand that ...
2
votes
2answers
388 views

Why RSA uses {d,n} as private key instead of {e,n}?

While studying the RSA algorithm I referred to some books and some sites such as RSA (wikipedia) and all of them chose {d,n} as the secret (private) key and release {e,n} as the public key but as d ...
2
votes
1answer
284 views

Textbook-RSA meet-in-the-middle attack against other RSA based schemes?

A “meet-in-the-middle” (not “man-in-the-middle”!) attack on textbook-RSA was presented to me. The only requirements for it was that the attacker gets the output of RSA and the public key, and that the ...
2
votes
1answer
179 views

Why is verification using DSA slower than verification with RSA?

We read in literature that verification of a digital signature is slower using DSA than if we used RSA. Why is this? DSA parameter generation: choose prime number $p$ choose prime number $q$ such ...
2
votes
2answers
729 views

phi(P*Q) = (P-1) * (Q-1)

I was trying to understand RSA when I encountered the Euler Function. I do understand this: $\phi(P)$, where $P$ is a prime is $P-1$. However it seems that for a number $N$ such at $N=P\cdot Q$ where ...
2
votes
2answers
898 views

How to decrypt this RSA-like cipher

Suppose we have a RSA-type Modulus $n = pq$ with $p,q$ prime. We also pick a random public exponent $e$ with $\gcd(e,\varphi(n)) = 1$ and compute the private exponent $d$ with $de \equiv 1 ...
2
votes
2answers
332 views

Please punch holes in this authentication scheme

Folks, I am undertaking a crypto course in Uni. Our professor asked us to try and design some authentication schemes which are resistant to active attacks. This was just a in class exercise to get us ...
2
votes
2answers
193 views

It is reasonably safe to leave a SSH private key with a 30+ character passphrase public?

I'm curious about exploring uses for a distributing a single RSA private key with a passphrase instead of trying to secure the private key and distribute the public key. With the private key (and ...
2
votes
1answer
159 views

RSA Key generation Public exponent too big

I'm currently writing a paper about RSA (a self-chosen subject). I'm writing about the key-generation in RSA, and I have problem finding the public exponent e. I have chosen p = 61 and q = 53. Then ...
2
votes
2answers
603 views

Is RSA in a ECB-like-mode safe for bulk encryption?

Let's say I would like to communicate with my friend using asymmetric/public-key encryption, e.g. RSA. (Note: I do realize that in practice this is done through an intermediate symmetric key, but ...
2
votes
1answer
961 views

How to sign a message using RSA?

Assuming I already have a D, P, Q, etc of an RSA key: How do I now sign a message? If it matters – the message is around 100 bits. I don't know much about cryptography, but I can get these numbers ...
2
votes
2answers
3k views

How does a chosen plaintext attack on RSA work?

How can one run a chosen plaintext attack on RSA? If I can send some plaintexts and get the ciphertexts, how can I find a relation between them which helps me to crack another ciphertext?
2
votes
2answers
135 views

Publicly exposed hash of private key

Would exposing a cryptographic hash function's digest (e.g. SHA-3) of RSA private key data compromise the key? If so, what are the possible (cryptanalysis-) vectors for attacking the key if an ...
2
votes
1answer
204 views

What kind of machine can generate 100-400 digits prime number? RSA

The 64 bit machine's biggest number can be 2^63 (9,223,372,036,854,775,807). So what kind of a monstrous machine can generate 100-400 digits prime number? I probably don't understand something, so ...
2
votes
1answer
321 views

How does OAEP improve the security of RSA?

The heart of OAEP algorithm used for RSA encryption are the cryptographic hash functions $H$ and $G$. Does everybody (so also an adversary) know these functions? If YES: How does it help the ...
2
votes
2answers
415 views

risk of attacker decrypting RSA ciphertext without public or private key

As I describe in my previous question I am trying to decide if it's worth it for me to use the Offline Private Key Protocol in creating some long term private archives, instead of just going with a ...
2
votes
3answers
1k views

Is it safer to encrypt twice with RSA?

I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the ...
2
votes
1answer
382 views

Why do we need in RSA the modulus to be product of 2 primes?

I think I roughly understand how the RSA alorithm is working. However, I don't understand why we need the $N$, which we use as a modulus, to be $pq$ for some large primes $p, q$. I vaguely know it ...
2
votes
1answer
290 views

What is the strength of unpadded RSA?

I would like to use unpadded RSA for homomorphic encryption in a toy P2P game, for things like fair coin flips and shuffling. How many bits of security does unpadded RSA have, in relation to its key ...
2
votes
1answer
564 views

ABC Conjecture's Impact on RSA Encryption

A recent proof of the ABC Conjecture has been released by one Shinichi Mochizuki. Now, I'm not well versed in mathematics but it would appear that this proof implies that finding prime factors could ...
2
votes
1answer
715 views

Is RSA of a random nonce with no padding safe?

Consider the following protocol: Bob has a private RSA key $B_{priv}$, and Alice knows the public key $B_{pub}$. Alice wants to send confidential messages to Bob (no integrity intended). To send a ...
2
votes
2answers
349 views

Is it possible to figure out the public key from encrypted text?

Suppose Alice sends messages to Bob by encrypting the messages with Bob's public key. Eve knows that the data is encrypted using RSA, but does not know the public key. Can Eve figure out the public ...
2
votes
1answer
319 views

What algorithm does PGP use to encrypt email?

I know it uses RSA/DSA to create keys, but does it use that same algorithm for the actual cipher?
2
votes
2answers
135 views

Private RSA key for HMAC key

I am creating software tokens for future request authentication, and I want to use an HMAC for the token to make them tamper-resistant. To ensure I can check the HMAC later I need a secret, persistent ...
2
votes
1answer
149 views

Is it true that for RSA with no padding, the length of data must be equal to the length of key?

The question pertains not in terms of security but computing operational functionality, as it how the computation is done. Is it true that for RSA with no padding, the length of data must be equal to ...
2
votes
2answers
215 views

How to calculate the maximum output size for data encrypted with a RSA Private Key?

I have an an encryption algorithm I am working with that looks like this: prv_key_enc(sha1_hash(data)) Where, the RSA parameters are: RSA/ECB/PKCS1Padding 1024 ...
2
votes
1answer
185 views

Why can ECC key sizes be smaller than RSA keys for similar security?

I understand how ECC is based on the discrete log problem and RSA on integer factorization. I've read several references that show how a solution to either of these problems can typically be adapted ...
2
votes
1answer
142 views

Why encrypting with private and public keys produce the same result?

Let say $e = 5$, $n = 119$ and $d = 77$. If I encrypt, for example, $m=15$ I get: $$m_1 = m^e=15 ^ 5 \mod 119 = 36\qquad\text{and}\qquad m_2 =m^d= 15 ^ {77} \mod 119 = 36$$. Why? Is it always like ...
2
votes
1answer
276 views

Why does plain RSA not work with big messages ($m>n$)?

From what I can remember, RSA is something like this: Generate 2 distinct prime numbers $p$ and $q$ that have similar bit length. Compute $n=pq$ and $\phi(n)=(p-1)(q-1)$ Compute $e$ such that ...
2
votes
1answer
128 views

Which platforms are most vulnerable to Simple Power Analyse Attack

In a "Simple Power Analyse Attack", the difference in power consumption during multiply or square operation is used. In the RSA decryption process with the "Square and Multiply" algorithm, both ...
2
votes
2answers
1k views

What makes RSA secure by using prime numbers?

I am just learning about the RSA algorithm. Looking at the first two steps: Choose two distinct prime numbers $p$ and $q$. Compute $n = pq$. I have some probably stupid questions: Why do $p$ ...
2
votes
2answers
221 views

Chain several RSA encryptions without increasing the message size

I would like to be able to encrypt the output of RSA with RSA again without having the output grow in size over time. In other words, I have some data $D_0$ which I want to encrypt with RSA: $D_1 = ...
2
votes
1answer
218 views

Cracking an RSA with no padding and very small e

I have a project wherein I have to crack a given cipher text encrypted using RSA and have been given N and e. Can someone suggest an RSA attack using a very small exponent e(here e=3) and no padding?
2
votes
1answer
228 views

Is it possible to determine the group order by knowing the “public” and “private” key exponents in an RSA group?

I have an RSA group with modulus $n = p \cdot q$, two safe primes $p=2p'+1$ and $q=2q'+1$ and the "public" and "private" key exponents $d$ and $e$. $\phi(n) = 4p'q'$ is the order of the RSA group. If ...
2
votes
1answer
258 views

Are RSA signatures deterministic?

If I sign the word HELLO with the mechanism "NONEwithRSA" with the same private key, do I always will have the same signature? A Java example always return ...
2
votes
1answer
216 views

Why is RSA usually limited to messages up to 1 block

I'm wondering why RSA encryption usually is only used for messages that fit into one block. For larger messages hybrid encryption in combination with symmetric ciphers like AES seem to be the solution ...
2
votes
3answers
979 views

What is the length of an RSA signature?

Is it the same as the bits of the key (So a 2048 bit system will yield a 2048 bit signature)? At most as the key? Or something else entirely?
2
votes
2answers
2k views

RSA Proof of Correctness

Can anyone provide an extended (and well explained) proof of correctness of the RSA Algorithm? And why is it needed? I can't say that this or this helped me much, I'd like a more detailed and newbie ...
2
votes
1answer
579 views

“Signing” with public key

For this question, the following caveats and assumptions hold: There exists a 2048-bit RSA key pair used exclusively for signing/verification The private key is kept completely private There exists ...
2
votes
3answers
409 views

RSA finding the inverse of the public exponent

I have a very basic doubt in RSA key generation and its usage. In RSA key generation you choose two large prime numbers of a very large order. Then you multiply them.(eq $p \cdot q = N$) Now, ...
2
votes
1answer
48 views

Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers?

If we assume the strength of RSA is based on the difficulty of factoring (which I know we can't guarantee) and we compose the modulus of some other quadratic ring that is a unique factorization domain ...