# Tag Info

15

Suppose an RSA public key is still $(e, N)$ and the private key is still $d$. We have $Enc = (m*e) \text{ mod } N$ and $Dec = (c*d) \text{ mod } N$. The correctness of the scheme depends on the fact that $Dec(Enc(m)) = (m*e*d) \text{ mod } N = m \text{ mod } N$. This implies $e*d = 1 \text{ mod } N$. It is thus trivial to compute the private key given only ...

8

No, the security is about identical, as the underlying RSA problem is the same. Besides that, non-repudiation is usually managed differently with regards to legal requirements. Providing confidentiality (encryption) is a rather different use case than non-repudiation (signing a contract). It is also possible to use signatures for authentication rather than ...

7

Assumption: $e$ and $d$ are prime with $N$. If we use the multiplication instead of the power. We have $d \equiv e^{-1} \pmod N$ : \begin{align}c \times d &= m &\mod N\\ m \times e \times d &= m &\mod N\\ e \times d &= 1 &\mod N \end{align} (It has to work for any $m$ so we can suppose $m$ prime). $e$ and $N$ are publicly known, to ...

6

No, it is not easy! RSA is based on the difficulty of factoring the product $n=pq$ of two large prime numbers. But if you know $\varphi(n)$ for plain RSA you can compute the secret exponent $d=e^{-1}\bmod \varphi(n);\;$ and you can factor $n$ from the two equations $n=pq,\;\varphi(n)=(p-1)(q-1)$.

6

Any probabilistic signature scheme can be made deterministic without any loss of security. The generic transformation is as follows: Let $(pk,sk)$ be the key-pair of the original signature scheme Choose a random key $k$ for a pseudorandom function $F$ (you can use HMAC or CMAC), where the output of $F$ is enough randomness used to sign. This key is part of ...

4

No, neither of the two blocks of 6 equalities in the current version of the question are correctly describing either a trapdoor one-way function (first citation); or its use for public-key encryption; or signature of a message using a one-way hash and RSA (second citation). The two citations are only distantly related. In particular, the "one-way hash" in ...

4

What's the size of a 4096 bit private key? It depends. The range goes from 512 bytes (only $d$, no formatting, no encoding) up to 5632 (full parameter set, maximal $e$ size, no formatting, hexadecimal encoding) bytes for two-prime RSA. If you also consider multi-prime RSA, the range is much wider. So what influences the size of the stored private key ...

3

For private key operations you need at least $n$ (the modulus) and $d$ (the private exponent). The primes $p$ and $q$ let you calculate those – or use some shortcuts for quicker computation – so they also suffice. In practice RSA keys often include all of those values, to avoid having to compute them as needed and to allow for optimized and unoptimized ...

3

First of all, the usual way to do this is to generate a new random AES key and then wrap it with the public key. Generally you don't encrypt with the private key at all. Yes, SHA-256 is a one way hash so you can do this. The problem is that you would still need to encrypt with a public key to let the other party know the AES key (unless you use the key to ...

3

I'll give a brief and simple example of what is described in the quote, which is now known as RSA for which there are plenty of descriptions and tutorials for all levels of understanding as pointed out by yyyyyyy. ... so I thought of the product of two primes ... So, for our example this will be $p=21$ and $q=23$ of which the product is $n=21\times ... 3 This feels like homework, and so I won't give you the answer; I'll give you hints: If F(x) = x^e mod n, and (n, e) pair is public, will the first 1024 bits of both plaintext and ciphertext be enough for Eve to read the entire message? If Eve knows the first plaintext$M_0$, and the ciphertext$M_0 \oplus (r^e \bmod n)$, how can Eve recover$r^e \bmod n ...

3

Textbook RSA encryption (which just consists of modular exponentiation) is not secure. Furthermore, it operates on integers (numbers) rather than bytes. So you need some scheme of converting bytes to these integers. Furthermore, to provide the necessary security, you need some kind of padding scheme. Various RSA schemes are present in PKCS#1. Currently ...

3

RSA private key operations with $b$-bit keys scale as $\Theta(b^3)$ while public key operations scale as $\Theta(b^2)$. The reason public key operations are faster is that you can use a small constant $e$, e.g. $65537$, while $d$ will be as large as the modulus. So private key operations with a 16384-bit key will take about 512 times as long as for a ...

2

Your suggested formalization is not quite right. Also your notation isn't consistent with Schneier's. Schneier calls the hash function $f$, the input $x$ and the trapdoor $y$. The hash value of $x$ is the image $f(x)$ of $x$ under $f$. In general it is very difficult to compute $x$ just from $f(x)$. There is an efficiently computable function $g$, however, ...

2

If attackers can strip off RSA / EC / -DSA digital signature and conduct CCA on AES-CTR or CBC payload, why can't they do the same for AES-GCM? The scenario, you're talking about is iMessage or Signal Protocol or other protocols which allow optionally to sign the ciphertext and thereby don't MAC it. The problem here is a) that you could replace the ...

2

First of all, you should make a more formal definition of the protocol. Security cannot be assessed without a proper definition. Second you don't specify an key sizes. RSA-512 is such a low key size that it may be considered broken. On the other hand, you may run into performance issues if you choose a higher key size (Elliptic Curve crypto would make more ...

2

You're fine. There are several different padding methods listed in PKCS v1.5. The method that has active attacks is actually a padding used during public key encryption - that is, it's used to encode the plaintext message before handing it off to the RSA public function. We don't use that method to sign messages. For that matter, the attack model used ...

2

This is homework, and so I won't give you the answer outright; I will give hints: Hint 1: how could you efficiently generate a random pair $x_1, y_1$ with $x_1^e = y_1$, without resorting to the Oracle? Hint 2: how could you use the above observation to accelerate your algorithm?

2

How does value of $p$ comes to $2^{512}$ for security complexity of $2^{72}$? Personally, I couldn't connfirm this number, but rather landed at $2^{66}$. If you don't know how to find this number, just plug the $2^{512}$ into the complexity equation given and take the logarithm to the base two for better readability. Note that Schnorr's complexity ...

2

No its not secure. As this is homework my hint is: Textbook (plain) RSA encryption is deterministic, and so encrypting the same message always gives the same...

2

I will assume that Alice uses $D' = E^{-1}(\varphi(N) - 1)$ with $E^{-1}$ the inverse of $E$ modulo $\lambda(N)$. The question uses a very specific definition of $D'$, which requires the assumption that $E$ divides $\varphi(N) - 1$. But since such an $E$ is necessarily coprime to $\varphi(N)$, it is a special case of the more general definition of $D'$ ...

1

You are correct; your "proof" is invalid; even if you show that $d$ is the correct value modulo $e$, that doesn't immediately imply that it is the correct value. If you replace $d$ with $d+e$, that is also is correct modulo $e$, but is also obviously wrong (it is even). Instead, here is a better line of reasoning: Two integers $d, e$ work as the private, ...

1

The https://www.keylength.com/en web site summarizes reports from well-known organizations to give cryptographic key length recommandations for different kind of algorithms. Also note that The lengths provided here are designed to resist mathematic attacks; they do not take algorithmic attacks, hardware flaws, etc. into account. Plus, there is a ...

1

Ok, suppose that we have a ciphertext $(c_1, c_2, ..., c_8)$ that we wish to decrypt. What we start off with is to make a guess for $p_8$, which is the decryption of the last byte of the block. Suppose that we guess that it is 0x07; we then need to validate that guess. What we do is create a two block message; the second block is the challenge ciphertext ...

1

I am currently hoping to find an answer to a similar problem, but maybe I can share some ideas. I would say that your problem is more standard than mine, and therefore it has the benefit that the existent options are relatively standard. However, my own question made me realize that key storage is an information security problem, as opposed to a ...

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