# Tagged Questions

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.

4k views

### Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512

Assuming in the future there was a functioning 1024 qubit quantum supercomputer and it could run Shor's algorithm or Grover's algorithm to crack encryption very quickly. I'm interested in how the ...
134 views

### Does RSA have two trapdoors?

I watched some videos from Khan Academy explaining the algorithm for RSA encryption/decryption. They explained that there are two trapdoors, modular exponentiation being one and prime factorization ...
137 views

### Relationship between exponent and modulus in RSA (as RSA properties as listed in X.509)

In one of my assignments, I had the following question (Please read on. Not a homework assignment :) ): X.509 (1998 version) lists properties that RSA keys must satisfy to be secure. One such ...
106 views

### RSA algorithm private key extraction

Decrypting messages can be done by using the following formula: $$M = C^d \mod n$$ Where $M$ is the decrypted message, $C$ is the encrypted message and $d$ is the private key Theoretically speaking,...
286 views

### Is there any reason to use RSA or DSA when we have ECC?

I am having trouble coming up with a use case for RSA or DSA. It appears that ECC is better in every way. Is this true? I am looking for cases where RSA/DSA is superior to ECC, not where it is used ...
139 views

### How to attack RSA-CRT with large public exponent?

Suppose we have $(n,e)$ and the ciphertext $c$ where the public exponent $e$ is of the same length, 1023-bit, as the modulus $n$. It is also assumed that the factors of $n$ are balanced. The message ...
168 views

### Help understanding basic Franklin-Reiter related message attack

I am trying to understand this attack at the most basic level. I set up the following basic scenario: Let the public encryption exponent, e = 3. Let p, be some arbitrary but known (to the ...
99 views

### How to decrypt RSA if ciphertext is less than the modulus and e=3?

I'm given a public key. Using openssl rsa ..... I got the public key has the exponent as 3. When I calculated the size of the ciphertext, it is 8 bits smaller than the 2048-bit modulus. How can I ...
24 views

### Is RSA safe anymore? [duplicate]

Some people may have heard of Shor's algorithm. It allows for integer factorization on a quantum computer. This wasn't a problem a little while ago since we didn't have any quantum computers. Google ...
38 views

### Key sizes for RSA over elliptic curves

I know that it is possible to define RSA over elliptic curves just as DSA and Diffie-Hellman have been. I know that it doesn't offer much of a speed advantage, but does it at least reduce the size of ...
90 views

### Can RSA with padding detect all errors in ciphertext?

I'm new in cryptography and there are a couple of things that i'm not sure if i understand correctly. First, when using padding (PKCS or OAEP), if the chiphertext has errors in transmission we'll we ...
127 views

### Can RSA (theoretically) be used as a block cipher?

Assume AES gets a devastating attack making it unusable. Is it possible to use RSA in a secure way that can encrypt data in bulk? I can't see how RSA (assuming OAEP padding) can be used in normal ...
114 views

### Choosing which is public vs private key

When I calculate two RSA keys, what if anything, would make any difference which I call the public vs which I call the private key?
250 views

### Why are recomended RSA key lengths so high? [duplicate]

I was checking for authoritative sources to back up my recommendation of a minimum RSA key length of 1024 and was shocked to find that NIST 800-56Br1 and FIPS 186-4 both recommend at least 2048 bits ...
62 views

### RSA : Double-Encryption and order of Encryption

I'm studying cryptography and we're looking at RSA. We're required to do a double encryption from Alice to Bob and then Bob back to Alice. We've been told the order of encryption is important and it ...
256 views

### What is the typical block size in RSA?

If the input text is divided into a fixed block size for encryption and decryption, what could be the typical block size for RSA algorithm for different size of input like 8 MB, 16 MB, 126 MB and 256 ...
172 views

### RSA private key finding method

Bob uses RSA with $p=83$ and $q=103$. His public key is $e=445$. Alice claims that she can calculate Bob's private key without using the definition $d=e^{−1}\bmod φ(n)$? But how?
86 views

### Why is AES-128 considered secure while RSA needs a 1024-bit size to be considered secure [duplicate]

I got asked this question today and I didn't know the answer, AES-128 is considered secure, the key size is 2^128, so you would need in average 2^127 tries to break the key. Why does RSA need at least ...
255 views

### RSA PKCS#1, v1.5 padding output

If I make use of RSA PKCS#1 in v1.5 what padding length is used. Basically, it is not allowed that the plaintext is bigger than the modulus. But what if the length in bits is the same (padding to ...
119 views

### Common Modulus Attack not reproducible

I want to calculate a simple example of the RSA common modulus attack. However, the result is not correct and I do not find my mistake. p=$29, q=37, n=p*q = 1073, \phi(n) = 1008, e1 = 5, e2 = 11$ ...
105 views

### How to encrypt incomplete block with RSA as a block cipher?

I have a question about an RSA academic example. If we are using block-RSA with a block-size of 3 and we have this message: "android". It is broken into 'and', 'roi', 'd'. How to encrypt the last ...
3k views

### How many RSA keys before a collision?

I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a ...
144 views

### How to determine if padding has been used while encrypting a message with RSA?

I am trying to decrypt a RSA encrypted text file. I have a 2048 bit public key. Analyzing the public key with openssl reveals the exponent used is 3. ...
443 views

### MiTM on RSA public key encryption

a) Alice just generated a new pair of public and private RSA keys (pkA , skA ) = ((N, e), d) and would like to start a private conversation with Bob. How can Alice interact with Bob and exchange a ...
270 views

### Key exchange and man in the middle issue. Secure solution

I am trying to design MiTM protected key exchange algorithm. For instance I am using RSA asymmetric keys. Alice and Bob respectively have each their own pair of keys. And they should be able to ...
3k 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 updater,...
106 views

### Is this a good communication scheme?

I'm writing a wrapper for a chat program to allow for end-to-end encryption. I'm using Python and PyCrypto to accomplish this. I'd like to use a well known library to do this, but to my knowledge, ...
68 views

### RSA numerical questions

Let $n$ be the modular arithmetic, $p$ and $q$ the two large primes such that $n=p*q$ and $e$ the public exponent. Here they are two "simple" numerical questions: If $p = 13$ and $q = 17$, what is ...
128 views

### Why does the time complexity of RSA encryption and decryption depend on the size of the modulus?

I would think that the time complexity would depend on the exponent, not the number of bits in the modulus. For example, if the exponent were 5, using the "naive" method, we would perform 5 ...
174 views

### How to convert RSA public keys to one key to use for text hashing?

I've recently asked a question about RSA encryption. One of the things that I don't understand is the usage of two public keys. In the example on Wikipedia, a message is encrypted like: ...
98 views

### How can a message encrypted with the public key be decrypted with the private key? [duplicate]

I've been reading about encryption and have a basic understanding of the concept. What I don't understand, however, is how a calculation with one key can result in a number that, through calculation ...
190 views

### What is wrong in the following algorithm for computing a hash function using RSA?

I'm studying for a cryto exam and have run across this question which has stumped me. What is wrong in the following algorithm for computing a hash function? Take a message $M$, generate a random ...
103 views

### Plaintext and ciphertext block sizes

How can you determine the largest plaintext block size and smallest ciphertext size if you used RSA with $n=59768553302699443$ using an alphabet with $27$ characters?
78 views

### Preserving Confidentiality and Integrity in a Public channel

Let's say I've got two people that are trying to talk in a public channel $A$ and $B$ and they want to preserve their confidentiality and integrity. Which cryptographic algorithm would they want to ...
123 views

### Complexity using RSA

You encrypt a message using the RSA encryption system as $t^e \pmod n$ , where $t, e < n$ and $t$ is the numerical equivalent of the message. The message is written in a $27$-letter alphabet and is ...
141 views

### Encryption scheme like RSA where encryption is the inverse of decryption

In RSA, it is basically equivalent to use the private key $d$ to encrypt as it is to use the public key $e$ to encrypt. They are exactly inverses: $e=d^{-1}$. I need to know, are there other public ...
108 views

### splitting the plaintext and ciphertext into blocks

Say I was to use RSA with a given value of n. I choose to split the plaintext and ciphertext written in a 27 letter alphabet into blocks with k and m characters resp. How would I find the largest ...
52 views

### Computing the cardinality of the co-domain of specific modular exponentiations

Consider the following function: $f: \mathbb{Z}_n \rightarrow Y,~x \mapsto x^e \bmod n$, where $n = p \cdot q$ is an RSA modulus and $gcd(\varphi(n),e) \neq 1$ (different as required for a public ...
151 views

### Session key Exchange, some doubt

I have to find a solution to this problem: I have a network composed by 1 server and some client. The server has a couple of keys (public and private) and it shares a secret key with each client. My ...
63 views

### Defining Symmetric vs Asymmetric cryptosystems

I'm writing a project on the advantages and disadvantages of symmetric vs asymmetric cryptosystems. At the moment I am trying to define both systems using mathematical notation. Under the heading "...
281 views

### Should I use RSA encryption since RSA is said to be broken by NSA? [closed]

I am developing a simple web app that uses asymmetric encryption, but I am not sure whether to chose RSA for the reasons mentioned above. What are your suggestions? Also if I decided to go with RSA ...
219 views

### Lattice based attack on RSA

Let $n=pq$ be the RSA module and at least one of $p,q$ is a weak prime.It is proved that the number of such $1024$bit $n$ is at least $2^{759}$. With lattices we can factor these $n$ in a second (I ...
241 views

### $m ∈ Z_n \backslash Z^*_n$, RSA works but not secure

If you happen happen to have a message $m ∈ Z_n \backslash Z^*_n$, RSA works but not secure. How likely is it going to happen? $|n|=1024$ bits $|p| = 512$ bits $|q| = 512$ bits.
56 views

### compact rsa private key format

As shown in Why does my SSH private key still work after changing some bytes in the file? a typical RSA private key file contains. The public modulus $n$ and exponent $e$; The private ...
122 views

### RSA: Proving that $p+q-1 < 3 \sqrt{N}$, where N = pq and p,q are prime?

I'm doing some research into attacks on the RSA cryptosystem and have stumbled across Wiener's attack. Within the proof there exists the statement "$p+q-1 < 3\sqrt{N}$". No proof is given for this,...
592 views

### Why can’t the public key exponent in RSA be negative?

I am looking at why certain public keys in RSA can't be used, such as: 2 and all other even numbers (since $\gcd(\phi,e)$ must equal 1) 1 (since the cipher text would equal the message) 0 (since the ...
136 views

### Encrypt letters separately?

I am trying to encrypt the word Hello using RSA. When encrypting Hello’s integer representation, is each letter encrypted ...
61 views

### How to calculate d in RSA for my number with this [duplicate]

I took the p&q value as 61 & 53 and n=3233 e=17 d=? How to find it? Plz help me...