New answers tagged

0

The overhead of PKCS#1 v1.5 padding is at least 11 bytes. 8 of these bytes are a random value in the range [1..255]. This makes it unlikely that the same ciphertext is generated for identical plaintext input. Note that the padding is placed before encryption. The output size will be identical to the modulus size (in bytes, rounded downwards, if applicable). ...


1

The problem is to reliably and efficiently find message $m$ (with $0\le m<n$) given RSA modulus $n$, distinct RSA public exponents $e_1$ and $e_2$ coprime to each others and to the unknown $\phi(n)$, and ciphertexts $c_1=m^{e_1}\bmod n$ and $c_2=m^{e_2}\bmod n$. WLoG, and per the corrected question, $y_1$ is negative when it is applied the extended ...


2

With such a small block size there is no way to employ RSA padding modes such as PKCS#1 v1.5 padding or OAEP. You could however see the encryption as ECB mode encryption. In that case you could apply padding mechanisms that have been constructed for symmetric block ciphers. Those padding modes however have been defined for bytes rather than characters. ...


0

You can actually "invert" a value m with respect to n even if $$gcd(m,n) \neq 1$$ You are looking for a value $m^{-1}$ that satisfies $$m*m^{-1} = 1 \pmod{n}$$ This is a linear congruence. You need a bit more time to solve than just simply inverting a number. But by trying all the possible values as specified in the link above, you will finally ...


1

This is an issue with any block cipher. One solution is to pad the message. This means that, first you split it into blocks and then you will have some remaining characters at the end that are not one whole block. So lets say that the block length is L and you have n characters. You can add at the end of your message L-n extra characters so that with those, ...


2

In real word RSA modules are so large that probability for finding $c_1$ which is not coprime with $n$ is approximately zero. Also if you founded such number then $p=gcd(c_1,n)\neq1$ so $p$ is a factor of $n$ and in this case attack is not necessary because $n$ is factored. $gcd(296,1073)=37\neq 1$ so $p=37,q=\frac{1073}{37}=29$ and $\phi(n)=1008$ Now ...


-1

Now the standard key size for RSA is recommended of 2048 bits. This is large enough to never having a collision in practice, where brute force is 2^{2048}. Even if we consider some attacks that allow to break it with half the key size or in birthday attack, this number is quite secure. However, larger the key size, more overhead and lower efficiency.


2

You need an authentic channel from Alice to Bob to get a secret channel from Bob to Alice. This assumption is missing in a), so anyone in control of the communication channel can play man in the middle on any protocol. As long you don't have a secret channel from Alice to Bob or an authentic channel from Bob to Alice, Alice will never (= for any protocol) ...


0

It is not safe at all since Factoring as a service project (https://github.com/eniac/faas) together with Amazon EC2 allows the factorization of a 512-bit key for less than $100 in only a few hours.


0

Nobody (at least, nobody who does crypto seriously) splits up data into blocks to be independently encrypted with RSA. Not only is this inefficient, in CPU and in network bandwidth (because asymmetric encryption necessarily implies data enlargement), but we do not really know how "safe" it is. This is a little-studied question, so there is no accepted ...


0

Solving for $D$ in this case is known as the discrete logarithm problem. This is a known hard problem, as there are no known algorithms to calculate it in polynomial time. In other words, as the size (i.e. the number of digits) of the numbers increase, the time it takes to calculate gets higher exponentially. For this reason, it's used in cryptography as a ...


2

what is the range for exponent e? Actually, there is no required upper bound for $e$ (except that some implementations may reject ridiculously large values). The math behind RSA states that any $e$ that is relatively prime to both $p-1$ and $q-1$ will work, no matter how large it is. There might not appear to be a need for an $e > lcm(p-1, q-1)$ (as ...


0

As explained on this page you have: $1 < e < \phi(n)$ so with the specific values you mentioned we have: $\phi(n) = \phi(p \times q) = \phi(p) \times \phi(q) = (p-1) \times (q-1) = 12 \times 16 = 192$ (see Euler's totient function definition) The threshold on the maximum integer you can encrypt is $n-1$ which is $76$ if $p=7$ and $q=11$. Note that if ...


2

1a lHash: What is this and where does this come from? That's in PKCS#1 v2.1: RSAES-OAEP-ENCRYPT ((n, e), M, L): 2a. If the label L is not provided, let L be the empty string. Let lHash = Hash(L), an octet string of length hLen (see the note below). 1b) PS: A string of zeros, but how much zeros? Similarly for this question, lets ...


3

That doesn't hide Bob's identity from eavesdroppers. (The OP mentioned in chat that the OP isn't trying to do that.) I can no longer spot any other problems with the key exchange part. The encryption/decryption of application level data is vulnerable to arbitrary replays and reflection and dropping. ​ The public MAC input should indicate direction and ...


1

Perhaps a simplified example or two might help you intuitively understand the concept. Let's say you want to let your little brother and sister encrypt messages so that either of them can encrypt any message, but only you can decrypt them. To keep things simple, let's say that the messages are simply numbers from $1$ to $10$. Your siblings have been ...


2

Theorem: Let $gcd(a,n)=1$ and $\phi(n)$ be Euler's totient function, then $a^{\phi(n)} \pmod n=1$. One of this famous methods for encrypting is RSA. In this method we use above theorem. Let $e,n$ are public and $\phi(n) , d$ are private such that $e\cdot d =1\pmod {\phi(n)}$$(e\cdot d=1-t\cdot \phi(n))$. For encryption we have: ...


0

There is a paper by Daniel Bleichenbacher and Alexander May called "New attacks on RSA with small secret CRT-Exponents" (you can find it under http://www.cits.rub.de/imperia/md/content/may/paper/crt.pdf). They are not quite able to break the RSA under your assumptions. I'm not aware of better results, but I didn't look at the list of articles citing this ...


0

In his paper, Wiener suggests using large values of $e$ when the exponent $d$ is small. When $e>N^{1.5}$, Wiener's attack will fail even when $d$ is small. Boneh and Durfee attack is an improvement for Wiener's attack. With this attack you can decrypt $c$. This attack use $LLL$ algorithm. For more detail you can see "Cryptanalysis of RSA with Private ...


2

RSA modules factoring are not hard in general case. In special cases we can factor numbers easily. One of these special cases is weak prime number, if at least one of two RSA modules primes is weak we can factor it easily. It is interesting that number of such $1024$ bit modules are at least $2^{750}$ and for $2048$ bit is $2^{1500}$. Your mentioned RSA ...


4

The field of cryptography that you are looking for is called Kleptography. In kleptography, we are dealing with a setting where the device performing your cryptographic tasks is potentially malicious. Now this device tries to leak information to some attacker that allows this attacker to break the used cryptographic scheme. If I am not mistaken that scheme ...


0

For a simple reason; for verification, the other side needs your private key K. Without knowing the K, no one can generate the 240 bits.


9

Hash functions must be public, so if you want use RSA as hash function you should fix $K$. Now let $n$ be the RSA module and $H$ denote RSA hash function. We have $$H(M)=H(M+n)$$ so this function is not second preimage and collision resistant. Also this system is not first preimage resistant (with known public and private key): Let $M^k=h \pmod n$ ...


10

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key. The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve): The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good. He ...


3

With an alphabet of 27 characters, the maximum number of characters that can fit into one plaintext block is equal to the largest integer less than or equal to $\text{log}(n) / \text{log}(27)$: $$\bigg\lfloor\frac{\text{log}(59768553302699443)}{\text{log(27)}}\bigg\rfloor = 11$$ On the other hand, assuming the ciphertext is represented as a string of ...


2

Which cryptographic algorithm would they want to use? That will really depend on the situation. To select the algorithms one should ask himself (at least) the following questions: Which standards do you trust? Which standard do you have to use? What computations can you afford? Symmetric, or public key based? It again depends on the situation. ...


2

Is javascript RSA signing safe? …is safe or can people forge… In contrast to the accepted answer, I would not call it “safe” from a cryptographic point of view and I would definitely not say that “ if you take good care of securing your environment where you run the JS code you will be OK. ” because the sad fact is: that’s not enough to ensure ...


2

What you seem to be looking for is a scheme like the following: It consists of two algorithms, a key generation algorithm $K$ and a "key use" algorithm $U$. The key generation algorithm outputs a pair of keys $(k_0, k_1)$. The "key use" algorithm takes as input a key and an element from some set $S$ (which may depend on $k_0$ and $k_1$), and outputs an ...


4

One way to approach this problem is to first look at the simpler problem of that cardinality of $x^e \bmod p$ where $p$ is prime, and $gcd(p-1, e)$ might not be 1. In that case, we have two cases: $x \equiv 0 \pmod{p}$, which makes it obvious that 0 will always be a possible postimage, and $x \in \mathbb{Z}^*/p$; in this second case, that group is ...


1

Preliminary on notation: in the question, it seems advisable to change $C=T_{k}M$  to $C=T_{k}(M)$ , and change $M=T^{-1}_{k}C$  to $M={T_k}^{-1}(C)$ it is necessary to change $T_{k}T^{-1}_{k}=I$  to ${T_k}^{-1}\circ T_k=I$ , meaning that the function obtained by applying $T_k$ then its inverse ${T_k}^{-1}$ is identity, with $\forall M, ...


1

I think it covers both symmetric and asymmetric systems. Given a transformation $T_k$, if computing $T^{-1}_k$ is easy then this is a symmetric cryptosystem. On the other hand, if this is difficult than it is an asymmetric one. Note that in this case, we are ''hard-coding'' the key $k$ inside the transformation. Thus we are just given the transformation ...


1

Your definition only covers symmetric encryption since the same "index" $k$ is used in $T_k$ and $T^{-1}_k$ (i.e., encryption and decryption use the same key) If you want to give a generic definition that covers both types of encryption, you could say that the transformations are $T_k$ and $T^{-1}_{k'}$ and that in the case of symmetric encryption $k'=k$.


15

This question has many problems in the way it was asked, and clearly did not come after doing some investigation. However, since this seems to be a misconception that is spreading widely, I will relate to it. It is not true that the "crypto community" (whoever that is) believes that the NSA can break RSA. In fact, if Snowden taught us anything, it is that ...


2

Yes, this seems to make sense and it is a plausible solution. The KEM approach does not work, unless you use some tricks, like including a hash of the message in the KEM. (That could work, of course.) Security goal The type of scheme we are looking at consists of three algorithms $(K,E,D)$. The key generation algorithm $K$ outputs two keys, say $k_0$ and ...


1

We know that $|\mathbb{Z}_n| = p\cdot q$ and that $|\mathbb{Z}_n^*| = (p-1)(q-1)$. So $|\mathbb{Z}_n \backslash \mathbb{Z}^*_n| = (pq) - (p-1)(q-1) = pq - pq + p + q - 1 = p + q -1$. That number is approximately $2^{513}$ given your example prime sizes. So, out of approximately $2^{1024}$ choices for messages $m$, quite a few are bad. That said, finding ...



Top 50 recent answers are included