Bitcoin : Cryptographic systems (RSA / ElGamal Encryption / Hash Encryption)

RSA (Rivest–Shamir–Adleman):

RSA is a widely used public-key cryptosystem for encryption and digital signatures. It relies on the mathematical properties of large prime numbers. Here's a simplified explanation of how RSA works:

• Key Generation:
  • Choose two large prime numbers, p and q.
  • Compute their product, n = p * q.
  • Calculate φ(n) = (p - 1) * (q - 1), where φ is Euler's totient function.
  • Select a public exponent, e, which is relatively prime to φ(n).
  • Calculate a private exponent, d, such that (d * e) % φ(n) = 1.
• Encryption:
  • To encrypt a message M, the sender uses the recipient's public key (n, e) to compute C = M^e mod n.
• Decryption:
  • To decrypt the ciphertext C, the recipient uses their private key (d) to compute M = C^d mod n.

RSA's security is based on the difficulty of factoring the product of two large prime numbers (n). If an attacker can factor n, they can compute the private key and break the encryption.

 

ElGamal Encryption:

ElGamal is another public-key cryptosystem, primarily used for encryption. It's based on the Diffie-Hellman key exchange and discrete logarithm problem. Here's a simplified overview:

• Key Generation:
  • Choose a large prime number, p, and a primitive root modulo p, g.
  • Select a private key, x, as a random integer.
  • Calculate the public key, y = g^x mod p.
• Encryption:
  • To encrypt a message M for a recipient, the sender generates a random integer k.
  • Compute the ciphertext (C1, C2) as follows:
    • C1 = g^k mod p
    • C2 = M * y^k mod p
• Decryption:
  • To decrypt (C1, C2), the recipient uses their private key x to compute:
    • s = C1^x mod p
    • Calculate the modular multiplicative inverse of s, s^(-1) mod p.
    • Recover the original message M = C2 * s^(-1) mod p.

ElGamal's security relies on the difficulty of the discrete logarithm problem, specifically the challenge of finding x given (p, g, y, C1, C2).

 

Hash Encryption (Hashing):

Hashing is a one-way mathematical function that takes an input (or "message") and produces a fixed-size string of characters, which is typically a hexadecimal number. Here's how hashing works:

1. Hash Function:
   • A hash function takes an input (message) and returns a fixed-length string of characters, known as the hash value or hash code.
   • The same input will always produce the same hash value.
   • Even a tiny change in the input will result in a significantly different hash value.
2. Properties of Hash Functions:
   • Deterministic: The same input always produces the same hash value.
   • Fast computation: Hash functions are designed to be efficient to compute.
   • Pre-image resistance: It should be computationally infeasible to reverse the hash function and recover the original input from the hash value.
   • Collision resistance: It should be unlikely for two different inputs to produce the same hash value.

Hashing is commonly used for various purposes, including data integrity verification, password storage (salting and hashing), and digital signatures. Hash functions like SHA-256 and SHA-3 are widely used in modern cryptography and information security.