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
1answer
500 views

How difficult is it to brute force d in RSA: d = (1/e) mod φ in a CPT attack?

Given that RSA key generation works by computing: n = pq φ = (p-1)(q-1) d = (1/e) mod φ If I was an attacker who wanted to brute force d, could I brute force d given just the public key, the ...
3
votes
1answer
497 views

Can you identify the public key used to encrypt something?

If I encrypt a string with a public key, does the encrypted ciphertext reveal the public key I used to encrypt it? Basically, I don't want anyone to know who the ciphertext is addressed to. I'm ...
3
votes
1answer
1k views

Secure encrypt-then-sign with RSA

I understand that when you want to encrypt and sign data with RSA the generally recommended approach is sign-then-encrypt. However, I have encrypted data that I need to sign, to prove the author of ...
3
votes
2answers
617 views

RSA private key format for Mega

I've been trying to reverse engineer Mega's (mega.co.nz) API calls. And stopped on the step where client needs to decrypt session id with provided RSA key. I can get key data, but I have no idea how ...
3
votes
1answer
178 views

Is this attack for RSA possible?

$N=p·q$ ($p$ and $q$ are prime numbers), $m_1, ..., m_x$ are the messages, $e$ and $d$ are RSA encryption and decryption exponents, respectively. I am given $e, m_1, m_1^e, m_1^d, ..., m_x, m_x^e, ...
3
votes
2answers
3k views

How do digital certificates work, and why is it not possible to reverse engineer one from a signed file?

Digital certificates are used quite commonly these days, for signing files. They are used by various operating systems to ensure reliability and security. For example, Android requires that each of ...
3
votes
1answer
1k views

Demonstrating the insecurity of an RSA signature encoding scheme

I'm working on problem 12.4 from Katz-Lindell. The problem is as follows: Given a public encoding function $\newcommand{\enc}{\operatorname{enc}}\enc$ and a textbook RSA signature scheme where ...
3
votes
1answer
192 views

Is differential calculus related to RSA?

I'm writing a high school math paper on RSA and I'm wondering if it's possible to relate calculus to RSA. Is calculus used for any part of RSA? It can be for proving equations/theorems, for generating ...
3
votes
1answer
311 views

Purpose of leading zero in PKCS1-v1_5 padding

According to this document the padded message has the following structure: $EM \;= \; 0x00 \; || \; 0x02 \; || \; PS \; || \; 0x00 \; || \; M$ What is the purpose of this null byte at the beginning ...
3
votes
1answer
2k views

RSA square and multiply

If an RSA encryption uses a modulus $n$ of 15000 bits and $e = 3$ or $e = 2^{16} + 1$, how many squarings and multiplications will we need for encryption, and for decryption? Could you please explain ...
3
votes
1answer
909 views

RSA key pair generation using PRNG with same seed

I see a lot of Q/A where persons are trying to generate a specific key pair using static data such as a password. Now say we use a known PRNG (dangerous assumption), seeded with a the data as a static ...
3
votes
1answer
156 views

implementing long term archive encryption

Let's say I want to create private archives for the long term (e.g. more than 30 ). The archives' sizes could be anywhere from 1 GB to 30 GB. As far as I understand I could go down two ways: The ...
3
votes
3answers
3k views

How do ciphers change plaintext into numeric digits for computing?

For example, in RSA, we use this for encryption: $ciphertext = (m^e \mod n)$ and for decryption. If our message is "hello world", then what number do we have to ...
3
votes
2answers
1k views

Proof of security for RSA signatures

I am new to here, I was having some problems with a problem I am working on: "For each of the following variants of the definition of security for signatures, state whether textbook RSA is secure ...
3
votes
2answers
726 views

Using an RSA private key simultanously as an AES encryption key to generate random numbers?

Currently I'm implementing a PRNG for an embedded system. Using the RFC 4086 I've decided to use the X9.17 - to be more specific the successor X9.31- standard to implement my PRNG. X9.17 uses DES, but ...
3
votes
1answer
359 views

RSA key pair generation and FIPS 140-2, 186-4

I need to securely generate RSA key pair and I need to have access to private exponent in order to process it further. What's the difference in FIPS 140-2 and FIPS 186-4 in connection with RSA key ...
3
votes
1answer
96 views

Client authentication on limited hardware

I'm developing a authentication and authorization protocol for a Bluetooth device. The device should communicate with an Android app and needs to be able to authenticate the app during the connection ...
3
votes
1answer
214 views

Are RSA or ECC vulnerable to an attack where the same (unknown) plaintext is encrypted with multiple public keys?

I'm not sure what this attack model is called - it's not known-plaintext and also not quite cipher-text-only. It is similar to this question except the general case (not just two keys) and using keys ...
3
votes
1answer
369 views

Should new applications still use RSA? Is it worth going down the ECDH route for protocols?

I am currently designing an application for communication between two and more users. At the moment I am trying to figure out what methods to use for the asymmetric cryptology. With the recent ...
3
votes
1answer
228 views

Safely use CryptSignAndEncryptMessage?

I am developing an application that sends messages which I want to encrypt and sign. The CryptoApi offers a function called CryptSignAndEncryptMessage. The description says, what this function ...
3
votes
0answers
97 views

Relations between RSA and DLOG, factoring and DLOG

Definition: (The generalized Diffie-Hellman problem) Let $n=pq$ for two large primes $p,q$. Given $x, x^a, x^b,n$, find $x^{ab}\pmod{n}$. (1) Is there a known reduction from the GDH problem ...
3
votes
0answers
102 views

Finding algorithm: desire RSA's uniqueness and ECDSA's space efficiency

I am asking for help in finding a signature algorithm with the following property: Given a message m and a private key prikey, ...
3
votes
0answers
109 views

How much plainext could be known without reducting security of RSA?

It is known, for example, that exposing 50% of most significant bits of RSA private exponent does not provide security risk (when a small public exponent it used). So how to qualify security ...
3
votes
2answers
219 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
326 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 ...
3
votes
0answers
115 views

RSA security assumptions - does breaking the DLP also break RSA? [duplicate]

Possible Duplicate: Would the ability to efficiently find Discrete Logs have any impact on the security of RSA? I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, ...
2
votes
2answers
176 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
2k 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
3answers
299 views

Is it possible to attack RSA with a WalkSat derivative?

We consider a large $n$-bit number $N$. We want to find a factor, if it admits any. For $m$ taking values from $1$ to $n$, perform the following three steps (actually, for each $m$, perform many ...
2
votes
2answers
566 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
2answers
239 views

Is there a way to systematically calculate the public exponent $e$ in RSA?

I'm learning RSA in one of my classes and we were given a problem: $p = 5$, $q = 11$ I have done the following steps: $n = 5 \cdot 11 = 55$ $\phi = (5-1)\cdot(11-1) = 40$ I know that to ...
2
votes
3answers
330 views

In RSA, why does $p$ have to be bigger than $q$ where $n=p \times q$?

In openSSL – during RSA key generation – if $q$ is bigger than $p$, they exchange them. Why is that?
2
votes
3answers
379 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
4answers
955 views

RSA with composite numbers

It has been said that RSA uses a modulus product of two prime numbers for security reasons. But does RSA even work correctly if we allow composite integers instead? I think that the answer is "NO". ...
2
votes
2answers
321 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
948 views

How does one deal with a negative “d” in RSA?

I'm trying to write my own RSA implementation using the textbook approach — which I know is not optimal — of picking primes $p$ and $q$, then computing Euler's totient $phi$, then randomly picking an ...
2
votes
1answer
3k views

What is the meaning of “trapdoor” in cryptography?

I do not really understand the meaning of a "trapdoor" in cryptography, so here are my questions: What is the meaning of trapdoor and how can I convert a word or string using a trapdoor in ...
2
votes
1answer
664 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
2answers
131 views

how to let other people respond to emails only decrypt-able with my private key

First of all I have to say it's a homework question but since I have no one to consult with, I ended up here :) Suppose a case in which you are the manager of a company and all employees encrypt ...
2
votes
2answers
584 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
2answers
2k 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
277 views

Can RSA signing be implemented on top of RSA encryption/decryption?

I need to use RSA-SHA256 signing. Unfortunately not all Microsoft CryptoAPI providers support that. It's possible that I might get a handle to a CryptoAPI provider that can just encrypt/decrypt with ...
2
votes
2answers
198 views

Perfect Forward Secrecy in TLS

I read that TLS does PFS using Diffie Hellman. However, DH can be used even without certificates - so how is DHE-RSA better than plain DHE? Is DHE a insecure algorithm, that DHE-RSA is needed?
2
votes
1answer
255 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
1k 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
1answer
1k 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
81 views

Present an attack for the combination of OTP and textbook RSA

Let $N=p \times q$ where $p$ and $q$ are two primes. Compute $\Phi (N) = (p-1)(q-1)$. Choose $e$ s.t. $1 < e < \Phi(N)$ and $gcd(e,\Phi(N))=1$. Compute $d = e^{-1}(mod \ \Phi(N))$. ...
2
votes
2answers
93 views

Do all attacks against PKCS1 v1.5 encryption require an oracle

As far as I know, all attacks against RSA PKCS1 v1.5 require an oracle; is that true? Or are there any other attacks against it which are able to break it without an oracle? Background: I need to ...
2
votes
2answers
66 views

Is it hard to recover $p$ from $k \phi(p)$?

Given $k\phi(p)$, is it hard to recover $p$? Here, $p$ is a large prime, $\phi(\cdot)$ is Euler's totient function and $k$ is an unknown integer. Or what's the complexity to recover $p$ from $k ...
2
votes
2answers
319 views

Toy public/private key example open to frequency analysis?

I've been looking at an online Public Key Encryption Example (summarized below). It seems to me that choosing cyphertext = plaintext^(key) mod n would produce the ...