We’re rewarding the question askers & reputations are being recalculated! Read more.

Hot answers tagged

9

No, unfortunately your well meant comparison with HMAC fails and RSA with SHA-1 - as defined for PKCS#1 v1.5 padding and PSS - is considered insecure. The construction of HMAC makes it near invulnerable to attacks on the collision resistance of the underlying hash. That is because it uses the secret key as input to the hash function to create the additional ...


8

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? No. Factoring numbers with special forms like that is easy. You have a Mersenne number, $n = 2^e - 1$, whose exponent $e = 2048$ is composite. Whenever $e = u v$, we have $2^u - 1 \mid (2^u)^v - 1 = 2^e - 1$, since in general $x - 1 \mid x^k - 1$. (...


6

Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python; def fast_power(base, power): result = 1 while power > 0: # If power is odd if power % 2 == 1: result = (result * base) % MOD # Divide the power by 2 power = ...


5

This is a harder question than that it looks. To perform "plain" RSA modular exponentiation you can simply use the private exponent and the modulus. However, for faster RSA calculations that use the Chinese Remainder Theorem (CRT) you need the prime values, exponents and modulus. For RSA CRT you don't need the private exponent. In principle you can ...


4

So signing using RSA with a key size of 2048 with a SHA-1 hash over the content should be regarded secure just like HMAC-SHA-1, correct? The practical answer is: No, this is still insecure with all deployed RSA-based signature schemes. If you're just asking about using existing tools to make RSA-based signatures, stop here: SHA-1 is bad news, and don't ...


4

First, we'll assume that $n_B > n_C$, and we'll assume that he has no knowledge of the plaintext messages (which, if $A$ uses randomized padding, which he ought, is an appropriate assumption, even if the adversary knows the text of the message). Then, if any of the 12 messages $\mathit{ciphertext}_i \ge n_C$, then he knows that message cannot be to $n_C$ ...


3

if I use $e=7$ (or another coprime like $11$) I can't compute $d$ You can use $e=7$. When $n$ is squarefree, a private exponent $d$ will work if (not: only if) $e\;d\equiv1\pmod{\phi(n)}$, that is by definition when $e\;d-1$ is divisible by $\phi(n)$. There are solutions to that if and only if $e$ is coprime with $\phi(n)$. The textbook systematic way to ...


3

ISO/IEC 9796-2 is a digital signature scheme giving message recovery. That is: able to embed some of the message in the signature, thus lowering communication or/and storage requirements. There are a lot of options: Total recovery is when the message is fully embedded in the fixed-size signature; this limits the message size to a certain capacity. This ...


2

$\text{modBits}$ is the length of RSA modulus $n$ for example if you have 17 as RSA modulus than it has $\texttt{10001}$ as base two representation and has $\text{modBits} = 5$ If you generate a modulus $n$ which is 2048-bit than the $\text{modBits} = 2048$. Keep in mind that, we say a number $n$ is 2048-bit when it is between $2^{2047} \leq n \leq 2^{2048}-...


2

I was told that you can determine the private key of an RSA encryption with the public key. Were they joshing me or can it be done? Yes, it can be done. What you have not been told is that to factor a public key (usually hundreds of digits) to find the private key, requires a time exponential in the length of the public key, therefore even a supercomputer ...


2

In OpenSSL 1.0.2 (and former) at least, based on its documentation and code of an implementation, the big picture is that RSA_public_decrypt with RSA_PKCS1_PADDING applies the RSA public-key transformation $S\mapsto S^e\bmod N$ where $S$ is the alleged signature, then checks that the outcome (considered as a big-endian bytestring of the same size as $N$) is ...


2

signing using rsa2048 of SHA-1 of the content should be regarded still secure No, at least because SHA-1 collisions are possible and can makes things trivially insecure. For example, using the prefix at shattered.io, it is trivial to make two PDF documents each with an arbitrarily chosen appearance when displayed and the same SHA-1 hash. Thus if Malory ...


1

Am I wrong? (where?) Yes, there is a small mistake in the way you are computing $d$: you need to compute $d$ as being the inverse of $e$ modulo $\phi(n) = (p-1)(q-1) = 60$. So, if you pick $e= 7$ (since you cannot pick $e = 3$ because it would be coprime with $\phi(n)$), you need to compute its inverse modulo (which is typically done using Euclid's ...


1

Using tricks As said by Natanael in his comment to your question: this is maybe possible when using elliptic curve cryptography, and is actually kind of used in Bitcoin to have the so-called "hierarchical deterministic wallets". If you want a rough idea of how this kind of child key derivation works, I refer you to this answer. While it might also be ...


1

I'm not sure to understand your question. If you're asking about unbounded number of public keys, you have to notice that it implies unbounded size for public keys (by a cardinality argument). If you are speaking about exponential number of public keys: you can do it artificially achieve this by adding to your standard and unique public key, a long string (...


1

TL;DR It's not possible, because there are way too many prime numbers. It's possible that there might be a database with some of these numbers, but not a database with all the possible numbers. There are just way too many prime numbers to fit them all in one database. How many 1024-bit prime numbers are there? To get a 2048-bit modulus you multiply two ...


1

Problem summary: in textbook RSA, it is given $N$, $\phi(N)$, and a ciphertext $c$. It is wanted the plaintext message $m$ and a private exponent $d$. If $e$ or $m$ was random, that would be infeasible. But usually, $e$ is small thus guessable, and $m$ is highly redundant/recognizable. Thus we can try to compute $$\begin{align} d_e&=e^{-1}\bmod\phi(N)\\ ...


1

The key point in RSA is the fact that inversion in modulo $|G|$ is hard, of course other groups are a priori okay to build a secure encryption scheme. For example $U_{pqr}$, with $p, q, r$ large primes seems to be okay. But it will be probably less efficient (keys and ciphertexts will be probably larger for the same level of security). Of course, it is not ...


1

Yes. You don't need to wait until the end of the computation to compute the remainder, you can do that in each step of the exponentiation; this way, the largest numbers you'll need to handle are twice the size of n. There are many algorithms to compute the exponentiation itself, the simplest is square-and-multiply.


1

Yes, it is possible to generate a self signed certificate. If you've got a private key that can sign with it using the required signature algorithm then that should always be possible. Tool usage (such as openssl, which can be used to generate self signed certificates) is off topic here, but basically you just create the To Be Signed (TBS) part of the ...


1

For RSA to work, we require that its public key function $x\mapsto x^e\bmod(p\;q)$ be a reversible mapping on $[0,n)$. With $p$ and $q$ coprime, that's equivalent (by the CRT) to $x\mapsto x^e\bmod p$ being a reversible mapping on $[0,p)$ and $x\mapsto x^e\bmod q$ being a reversible mapping on $[0,q)$. With $p$ and $q$ prime, that's equivalent to $e$ being ...


1

The SOG-IS Agreed Cryptographic Mechanisms, which incorporates many elements from the French RGS, states (§4.1): Note 28-SmallD. The size of $d$ should be close to the size of $n$. Note that this is guaranteed for a small $e$. We should have at least $d > 2^{n/2}$, where $n$ denotes the bitlength of the modulus. This is the usual advice which has been ...


Only top voted, non community-wiki answers of a minimum length are eligible