Public-Key Cryptography

• Public-Key Cryptography = assymetric cryptography

• Theory

  • Trapdoor function: easy to go in one direction but very difficult and practically impossible in the other direction.
  • Most trapdoor function reduces to the same problem in mathematics - hidden subgroup problem (this problem abstracts both integer factorization and discrete logrithm). See also an explanation here

• Usage

  • priv could decrypt messages encrypted by pub but not true for the oppsite;
    • Therefore, two sides to communicate require two pairs of priv-pub keys.

• InfoSec

  • Breaking symmetric-cryptography needs brute-force because its private keys are just bits without structures
  • Breaking public-key cryptography has more efficient approaches because those keys are mathematical objects with structures.
    • There’s space-time tradeoff but N-bit key has at least N/2-bit security, i.e. requiring $2^{N/2}$ elementary operations to break
    • Therefore, we could say 256-bit ED25519 key has the security level the same as 128-bit symmetric-cryptography key
  • Traditional computing power:
    • btc global hash rate ~ 500million TH = $500\ast 10^{12}$ hash / sec, ~ $2^{68}$ hash/sec, ~ $2^{93}$ hash/year
    • so > 2^10 year to crash it
  • Quantum computing power:
    • {{embed ((65d1e0f7-983f-4146-b755-7cc9a9ed898f))}}

• Example

  • RSA
  • Elliptic-curve cryptography (ECC) ED25519

• ssh-keygen

  • ssh-keygen -t ed25519 -b 384

• software/libsodium can be used for encryption/sign/hash/etc.