# Tag Info

1

we can arbitrarily choose an exponent $e$ as long as $\gcd(e,\phi(n))=1$. No. If we want any security, we further : Must NOT choose $e=1$, because that makes $x\to x^e\bmod N$ the identity function over $[0,n)$. Must NOT choose $e$ in a way revealing information about of $\phi(n)$ or the factors of $n$ beyond that $\gcd(e,\phi(n))=1$. For example we can ...

0

But what is the most appropriate choice for it? For public exponent $e$, small values are preferred like $\{3, 5, 17, 257, \text{ or } 65537\}$. With this, we can guarantee that the number of operations is low. We can control this with our choice. Of course, for the choice of $e$, we must have $\gcd(e,p)=1$ for any prime $p$ divides the modulus $n$. This ...

1

Shouldn't the other parameters have exactly the same requirements? Certainly not all other parameters. The vendor could set requirements for $e$, but they would be different. For the other key parameters, extra requirements would be unusual, and there could be a valid technical reason for them only if you are using gear (software or hardware) that the ...

5

The web article states ..a key generation program (produces) two keys. It is arbitrary which of these is made public and which is kept private. This second sentence is wrong, especially since it appears in a general discussion about "Asymmetrical-key algorithms" (sic: the closer usual adjective in the cryptographic literature is asymmetric, and the ...

0

No this is not generally true, it must be a misunderstanding. The private key could entirely contain the public key and the scheme still be secure, but clearly reversing the roles of the public and private keys in such a scheme would be trivially broken (as now the public key would reveal the private key). Apart from that it would often not even be clear ...

0

A:Xb+k-X1, Xb+k-X2 -> k1, k2 A:m0+k0, m1+k1 -> m'1, m'2 -> B B knows Xb+k (transmitted it in a previous message), X1, X2 (A sent those), hence he can compute k1, k2. Hence, he can reconstruct both m0, m1, hence the protocol doesn't have the security properties we're looking at... Now, you don't have to use RSA, however you really do have to use ...

0

For the inclusion proof you might need the trapdoor or the accumulated set. The exclusion proof can be generated without knowing the trapdoor. See this related question and answer. How can one generate inclusion proofs if knew the trapdoor, i.e. the factorization of $N=p\cdot q$? Let's $A$ denote the accumulator's value, $x$ be an item to-be-accumulated ...

1

No and Yes! For the inclusion proof you either need the trapdoor or the accumulated set. However, it is possible to generate exclusion proofs without knowing the trapdoor, i.e. the factorization of the modulus, $N=p\cdot q$, or the size of the group, i.e. $\phi(N)$. Let $A$ denote the accumulator's current value, $x$ an item, $g$, a generator of the group ...

0

So after trying a few examples with small numbers, it turns out that if message $m$ is a multiple of $p$, $m=a*p$ then $\gcd(y,n)=p$, where y the known ciphertext. The rest is easy to compute.

3

The standard criterion for security is indistinguishability under adaptive chosen-ciphertext attack, or IND-CCA2. What this means is that the adversary is given: the public key $(n, e_B)$, and an oracle that answers queries of the form: What is the plaintext for the ciphertext message $c$? The adversary's task is to find any pair of messages with a ...

3

Why is this not a problem? Because for two different encryptions the random integers are drawn independently and uniformly at random over the whole range of the multipicative group $\mathbb Z_N^*$ (in practice this is usually approximated as $[1,n)$). The RSA assumption now literally states that it's difficult to recover the random value from its textbook ...

0

RSA-KEM is not working as you described. RSA-KEM mitigates the attack that you have described, RSA-KEM simply as follows; First generate a random $x \in [2..n\hbox{-}1]$, $n$ is the RSA modulus. Encrypt the $x$, $c \equiv x^c \bmod n$ Send $c$ The other side will decrypt to get $x = c^d \bmod n$. Now both side has $x$. To derive a key both sides use a Key ...

1

Let's look at the decryption part of RFC 8017 for OAEP. Let's only look at step 3, as step 1 is called length checking, and step 2 is the step to perform modular exponentiation and integer to octet string conversion (or, rather interpretation). Step 1 can fail but is out of scope for this as it acts on the ciphertext itself, step 2 cannot fail, even though ...

4

No, it is not safe. There are several methods to compute $p$ and $q$ from $n$, $e$ and $d$. See appendix C of this document.

1

Let the modulus is $n$, the message $1< m < n$. In your textbook RSA the signature is $$s = m^{d} \bmod n,$$ where the $d$ is the private key. Let the target signature be $s' = s^{-1} \bmod n$ and $m' = m^{-1}$ Let expand $s' = s^{-1} = (m^{d})^{-1} = (m^{-1})^{d}$ Therefore $s'$ is the signature of $m'$. That is one of the many other reasons ...

1

Let's take a look at this from a higher level of view. In asymmetric cryptography, private keys provide some form of authentication. Let $(e, d)$ be a public/private key pair respectively of a secure asymmetric encryption scheme $E$, and let $c = E_e(m)$ be the ciphertext corresponding to the plaintext $m$. If one is able to recover $m$ from $c$, then it's ...

3

Actually you are both wrong, assuming that each user wants to authenticate themselves individually and / or establish private conversations between pairs. Unfortunately this is assumption is missing from the question. If everybody is using (EC)DH then they need a key pair each to setup communication by establishing a session key. That means 10 times 2 keys = ...

2

Depends if "between themselves" means that they are sort of in a simple group-chat scenario. Then one private-public-key pair (i.e. RSA) would theoretically suffice (not factoring in the security), because they can all encrypt messages with the public key and decrypt messages with the private key that they all have an identical pair of it. In actual group-...

0

Take the server’s public key. Parse the modulus and public exponent. (A public key contains the public exponent and modulus) Factor the modulus into ‘p’ and ‘q’ elements. Calculate the private key as normal. i.e. 1) calculate phi (p-1)(q-1) Carmichael’s totient 2) calculate d the private key as 1/e mod phi 3) celebrate

0

For small $N$, textbook RSA decryption is possible without factoring $N$ using the cycling method, (sometime called cycling attack; see this for a reference): initialize $M\gets C$ set $D\gets M^e\bmod N$ (otherwise said, encrypt $M$) if $D\ne C$, then set $M\gets D$ and loop to the previous step output $M$ and exit. Since encryption is a reversible ...

0

Hint: consider that as the problem of deciphering $c$ in textbook RSA encryption with public key $(n,b)$.

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 ...

2

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 ...

0

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 (...

0

The RSA paper is giving a simple argument in their IX-B section; Computing $\phi(n)$ Without factoring $n$ An attacker who can compute the $\phi(n)$ then he can break the system by computing the inverse of $d$ of $e$ modulo $\phi(n)$. They argue that finding $\phi(n)$ is not easier than factoring since it will enable factoring as follows; $(p+q)$ can be ...

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 ...

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 ...

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 ...

10

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 ...

-1

Your ciphertext is A3 BB 05 00 In RSA, the ciphertext is always larger than the original data. In this case, the keys are 32 bits, which is 4 bytes, and A3 BB 05 00 is four bytes

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)\\ ...

Top 50 recent answers are included