Skip to main content
Cryptography

Return to Answer

replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because the ciphertext $(u,v)$ in ElGamal has 2 integers, when $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer, and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe techniqueRSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by acclamation of the jury)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because the ciphertext $(u,v)$ in ElGamal has 2 integers, when $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer, and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by acclamation of the jury)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because the ciphertext $(u,v)$ in ElGamal has 2 integers, when $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer, and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by acclamation of the jury)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because there arethe ciphertext $(u,v)$ in ElGamal has 2 numbers instead of 1integers, ofwhen $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer, and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by a landslideacclamation of the jury)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because there are 2 numbers instead of 1, of about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by a landslide)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because the ciphertext $(u,v)$ in ElGamal has 2 integers, when $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer, and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by acclamation of the jury)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.
more on the status of the olympics
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because there are 2 numbers instead of 1, of about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins here, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption-and-decryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by a landslide)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because there are 2 numbers instead of 1, of about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA wins here),
    • decryption speed (ElGamal as usually practiced wins),
    • encryption-and-decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by a landslide)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because there are 2 numbers instead of 1, of about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer and requiring extra resources. That fact is not very relevant in practice:

  • A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
  • ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
  • There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including
    • public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
    • key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
    • encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
    • decryption speed (ElGamal as usually practiced wins),
    • combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
    • simplicity of a safe message padding for non-random message (ElGamal wins by a landslide)...
  • As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
  • That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611
Rematch public key size
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611
Answer "why is (it) a bad property"
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611
Source Link
fgrieu ♦
fgrieu ♦
  • 145.6k
  • 12
  • 319
  • 611