Hot answers tagged

12

I've been suggested to digitally sign it, thus, I have my private key, and I ship my application with a public key, and the application then uses the public key to check the QR code As long as you can live with the requirements for RSA (signature size, computation), that sounds like an excellent idea. Am I encrypting the whole message using the private ...


12

From this answer: The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with $n$. So, if factoring is the method of choice for breaking RSA, it doesn't seem like it really helps.


11

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key. Huh? I see two problems with the above statement; "Encryption"; using the word encryption implies that there's a way somehow to decrypt it. However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the ...


10

There are many advantages of MAC's over signatures. For signatures you need to use asymmetric key pairs. Public keys need to be trusted for this to work. Unfortunately establishing trust is not that easy. Furthermore you don't want to use a private key stored on, for instance, a smart card (which would require a PIN and would likely be too slow). Instead ...


9

Your problem is equivalent to solving $m^3 \equiv c \pmod n$. This corresponds to breaking RSA for $e=3$. We know no efficient way for doing that without factoring $n$. If you know the factors of $n$ you can compute the private exponent $d$ as $e \cdot d \equiv 1 \pmod{\varphi(n)}$ using the extended euclidean algorithm and then compute $m$ as $c^d$.


7

MACs have some advantages over digital signatures The component of the computational cost that is independent of message size is much higher for digital signatures, to the point of being an obstacle and requiring milliseconds or/and dedicated hardware. We know no signature scheme where both signature and verification of short messages are of speed any ...


6

No, your values for $e$ and primes are fine (well, at least for a toy example); $e$ is relatively prime to both $p-1$ and $q-1$, and that's the only hard requirement (not counting the security related ones, of course). I get $d=905$, as $5 \times 905 \equiv 1 \pmod{ \operatorname{lcm}((53-1),(59-1))}$; alternatively, you might get $d=2413$, if you do the ...


6

Due to poor use of notation, the question uses an incorrect (or at least incomplete) definition of textbook RSA encryption, which actually defines ciphertext $c$ for a given $m$ as:$$c=m^e\bmod n$$This can be read as: “ $c$ equals [pause] $m$ to the $e$th power reduced modulo $n$ ” where power or/and reduced can be left implied, and the pause emphasizes that ...


5

So if $m^e$ can be greater than n, then you can get duplicate ciphers for the same message. I'm not exactly certain what you mean, but: If you mean that one particular message $m$ might be encrypted in two different ways, no, that's not the case, at least, not in the way that you mean. If you have a specific value for $m$, $e$ and $n$, then $m^e \bmod ...


5

The formula at the heart of RSA is: $$x^{\lambda(n)} = 1 \pmod n$$ where $\lambda$ is the Carmichael function. In the case of two-prime RSA it's $\operatorname{lcm} (p - 1, q-1)$. $$m^{k \cdot \lambda(n)+1} = m \pmod n$$ We choose $d$ such that $e\cdot d = 1 \pmod {\lambda(n)}$. If $\operatorname{GCD}(e,\lambda(n)) = 1$ then there is exactly one solution ...


5

Say you want to encrypt "Hello World!" with RSA. The first important thing here is the encoding of that text. "Hello World!" as such cannot be encrypted since characters are a non-numerical concept. So an encoding is used convert the characters of that text to numeric values (e.g. the ASCII / Unicode table, but there are many others, especially for non-...


5

…what number do we have to put as $m$ in the RSA formula? There are three possibilities what $m$ can be. A full-sized random bit-sequence, e.g. a random sort-of-key which is roughly as large as the modulus and will be used to derive a symmetric key for message encryption. Some padded message. This would mean you'd first apply some padding to your message,...


4

The first hash is only used to hash the label. Most of the time the label will simply be empty, which means that a constant value can be used, identified just by the hash algorithm itself. Although the hash values may differ and may have any SHA-x value, they are generally set to SHA-1 - which is the default. Note that SHA-1 is considered secure for MGF-1. ...


4

To your questions: You are not encrypting anything. Signing something with RSA is basically the same algorithm as decryption but some things are different (see below). No. You can generate one keypair and then use it for encryption, decryption, signing and verification. To help you with your task: Getting this right is not easy. If you have no ...


4

It seems that the authors of Keccak sponge (the algorithm chosen to be SHA-3) do think their SHAKE functions can directly be used for simplifying OAEP and PSS: The introduction of extendable-output functions (or XOFs, pronounced zoff) is a particularly nice feature of the standard. A XOF like SHAKE128 or SHAKE256 can be seen as a generalization of hash ...


4

We have $y^2-1 \equiv 0 \pmod n$, meaning that $y^2-1 = (y+1)(y-1)$ is a multiple of $n$. $y \not \equiv \pm 1 \pmod n$ means that neither of $y+1$ and $y-1$ is a multiple of $n$. Now, clearly $\gcd(y-1,n)$ is a divisor of $n$; we want to show that it is not $1$ or $n$. It cannot be $1$, because that would imply that $n$ divides $y+1$, which we assume is ...


4

Well, there are indeed differences between the two standards, as you can see below: key pair generation X9.31 requires that $p-1$, $p+1$, $q-1$, $q+1$ all have prime factors between $2^{100}$ and $2^{120}$, and that $p$ and $q$ differ in at least one of the first 100 bits. These requirements are there to frustrate suboptimal factoring methods, ...


4

Can someone quote a protocol, application, etc, where the disadvantages of the MAC relative to digital signatures can be ignored? Your particular attack is of no interest if B has nothing to gain to claim that it got message M from A. As for concrete examples: the TLS record format, IPsec, SSH, the IES public key system; actually, any protocol that ...


3

ASCII is one way to encode an alphabet into integers, which in return are mostly represented in binary or hexadecimal notation. But of course there are many other ways to encode alphabets into numbers, and exactly how you do that is entirely up to you. For example you just have the letters from A to Z and got the string $s = s_0s_1s_2s_3....s_n$. Then you ...


3

Since $e$ and $(p-1)(q-1)$ are relatively prime, the extended Euclidean algorithm gives you integers $u$ and $v$ such that $$ eu + (p-1)(q-1)v = 1, $$ from which it is easy to deduce an integer $d$ such that $ed \equiv 1 \pmod{(p-1)(q-1)}$.


3

That tells us those problems are in BQP. This answer describes a way of reducing factoring to SAT. More elaborate approaches will give reductions from ​ RSA or ECC ​ to SAT. On the other hand, if there is a polynomial-time reduction from an NP-hard problem to ​ RSA or ECC ​ ​ then ​ ​ ​ BQP ∩ UP ∩ coUP ​ = ​ NP ​ .


3

Firstly, it's not co-prime to the modulus, so $\gcd(m,N)$ would be greater than $1$. Secondly, $N$ is the product of two (and only two) prime numbers $p$ and $q$, so if $\gcd(m,N)>1$, then you know $m$ is one of the factors (and prime factors) of $N$.


3

It depends on the application if base 64 is being used to represent keys. Many applications that implement/use cryptography have been originally designed in a time where ASCII based communication was commonplace. If you would directly use BER / DER - a binary encodoing of parameters - then you had a high chance of losing data. For instance, you would not be ...


3

Base-64 is simply a way to represent binary data using the ASCII character set. It's used because a single base64 digit represents a whole number of bits (6 bits), where each decimal digit represents ~3.3 bits, which can make conversion a little tricky. Being able to represent more bits per digit also means its more space efficient than decimal. It takes ...


3

Comments already pointed out, that encryption and signing are not the same and should not be exchanged deliberately. Of course in practice specifically for RSA, not PKE in general, and only in the textbook variant (no padding), encrypt/decrypt are bascally the same operations as sign/verify: For all of them, you just do modular exponentiations; and the ...


3

are the DH public values exchanged unencrypted? Yes, that are. After all, they are "public values"; there's no weakness in exposing them in the clear. Now, we do have to be careful that they aren't modified in transit (if they can be, then someone can perform a Man-in-the-Middle attack). We do that by having the server sign its key share (using the ...


1

From RFC 2985: The challengePassword attribute type specifies a password by which an entity may request certificate revocation. The interpretation of challenge passwords is intended to be specified by certificate issuers etc; no particular interpretation is required. This has also come up over at Information Security Stackexchange with the TL;DR ...


1

RSA is based on the Carmichael function $\lambda$ (or if you prefer Euler's totient function $\varphi$): $$x^{\lambda(n)} \equiv 1 \pmod n$$ for every integer x that is coprime to n. From this you trivially get: $$x^{k\lambda(n)} \equiv (x^{\lambda(n)})^k \equiv 1^k \equiv 1 \pmod n$$ and multiplying both sides with x: $$x^{k\lambda(n)+1} \equiv x \...


1

No, RSA encryption does not provide authenticity, regardless of the padding. This is for the simple reason that anybody can encrypt with the public key. This is irrespective of the asymmetric algorithm used. You need to sign the data to obtain authenticity. What AEAD does do is to protect e.g. against padding oracle attacks. These can be performed on CBC ...


1

A.Toumantsev had it right in his comment that 'it depends'; I'll try to expand on that. First of all, there's no one 'window method', there are a bunch of different variations, and which $w$ works best for you would depend on the exact version you're using. With the most basic window method, to compute $a^e \bmod p$, you: compute $a^0 \bmod p, a^1 \bmod ...



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