New answers tagged

1

Your $d$ is indeed incorrect. I get $d = 4235309647073$, using Wolfram alpha. As to python, use the builtin pow function with a third argument equal to the modulus. So message = 6 encmessage = pow(message, 17, 6000029000033) assert message == pow(encmessage, 4235309647073, 6000029000033) which will apply a smart algorithm like those in answers to this ...


1

Is there any possibility to make a successful verification with just modifying message and signature, and without modifying public-key ? One would certainly hope not. If you can, then you've just shown that the signature algorithm used is broken, and not to be trusted. For a signature method to be considered secure, then it is required that someone ...


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


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


16

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


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


-1

$$2360221=1117 \times 2113$$ $$\phi(2360221)=2356992$$ $$d\equiv e^{-1} \equiv 942797 \pmod{2356992}$$ $$C \equiv M^e \equiv 1637411 \pmod{2360221}$$


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


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


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


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


0

The problem with non-authenticated symmetric cipher modes is that they are PRP's. That means that - no matter what you do to the ciphertext - you'll get a valid and unique plaintext (not considering unpadding). This means that an attacker can change (part of) the outcome of decryption by altering the ciphertext. It can also lead to information leakage, e.g. ...


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


0

Yes, you're still secure. The current RSA PKCS#1 v1.5 signature scheme is still thought to be secure. So the following information in RFC 3447 section 8.2, describing PKCS#1 v2.1 still applies: Moreover, while no attack is known against the EMSA-PKCS-v1_5 encoding method, a gradual transition to EMSA-PSS is recommended as a precaution against future ...


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?


0

Those figures look fishy to me. Just looking at the RSA figures, well, RSA encryption should be much faster than RSA decryption - you have them at the same speed. The reason RSA encryption is (typically) much faster is that we can choose a small public exponent without affecting security; the typical value is 65537, but it can be made as low as 3. The ...


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


0

OK, so... The solution I have found, which satisfies exactly what I've been searching for, is based on OpenSSL. I have initially discovered and tested it through the PHP function openssl_private_encrypt (and equivalent openssl_public_decrypt). Since my goal was to implement this in .net project I'm working on, I have ended up with OpenSSL.Net wrapper for C# ...


0

I would explore the GPU option before spending money on specialized hardware. I have done something similar using CUDA where I was doing many ECC operations in parallel. The GPU was about 30x - 50x faster than the CPU. You could probably hash the data on the CPU and then use the GPU for the RSA exponentiation.


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

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


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


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


0

There is typically no private key on the client side. At a high level the process goes something along the lines of (this is a simplification, read the protocol specs if you want the fine details) The client sends the server a "hello" message with info on supported protocols and ciphersuites. The server chooses a cipersuite and protoocol version and sends ...


0

While there are many TLS configurations, I will describe the most common setup. The public key is fixed on the server side - it is the servers public key. Upon connecting to the server and receiving the public key, the client then validates the key by checking that it has not expired, that it matches the domain name of the server who sent it, and most ...


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


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



Top 50 recent answers are included