Lamport-Signature

Lamport-Signature.md

Lamport Signature javascript implementation

I have implemented a basic Lamport Signature, following the instructions provided in this video.

• The private keys are generated using randomBytes, a function which essentially serves as a wrapper for OpenSSL's RAND_bytes(). More information on the randomness of this function can be found at the following links:
  • https://stackoverflow.com/questions/43033412/how-random-is-cryptorandombytes
  • Node.js crypto.randomBytes - https://github.com/nodejs/node/blob/86d74a248bf82a862104ba2dc63ebc573fd69a4f/src/node_crypto.cc#L5543
  • https://www.openssl.org/docs/man1.1.1/man3/RAND_bytes.html
• SHA-256 is used for the hash function.

import { createHash, randomBytes } from "node:crypto";

const LamportSignature = () => {
  const rng = randomBytes;
  const bits = [0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01];
  const blockLength = 256;

  // s0 s1 / s0 s1 
  const secretKeyBuffer = Buffer.alloc(64 * blockLength);

  // p0 p1 / p0 p1
  const publicKeyBuffer = Buffer.alloc(64 * blockLength);

  return {
    generateKeys() {
      for (let i = 0; i < blockLength; i++) {
        const r0 = rng(32);
        const r1 = rng(32);
        const p0 = createHash('sha256').update(r0).digest();
        const p1 = createHash('sha256').update(r1).digest();

        r0.copy(secretKeyBuffer, i * 64);
        r1.copy(secretKeyBuffer, i * 64 + 32);
        p0.copy(publicKeyBuffer, i * 64);
        p1.copy(publicKeyBuffer, i * 64 + 32);
      }

      return {
        privateKey: secretKeyBuffer,
        publicKey: publicKeyBuffer,
      }
    },
    sign(message) {
      const signBuffer = Buffer.alloc(32 * blockLength); // 32 bytes * 256 blocks
      const hashedMessage = createHash('sha256').update(Buffer.from(message)).digest();

      for (let i = 0; i < blockLength; i++) {
        const messageByte = hashedMessage[Math.floor(i / 8)];
        const s_i = signBuffer.subarray(i * 32, (i + 1) * 32);
        const targetBuffer = messageByte & bits[i % 8]
          ? secretKeyBuffer.subarray(i * 64 + 32, (i + 1) * 64) // Note that s1 not s0
          : secretKeyBuffer.subarray(i * 64, i * 64 + 32) // s0
        targetBuffer.copy(s_i, 0);
      }
      return signBuffer;
    },

    verify(publicKey, message, signature) {
      const signBuffer = Buffer.from(signature);
      const hashedMessage = createHash('sha256').update(Buffer.from(message)).digest();

      for (let i = 0; i < blockLength; i++) {
        const s_i = signBuffer.subarray(i * 32, (i + 1) * 32);
        const messageByte = hashedMessage[Math.floor(i / 8)];

        const expectedPublicKey = messageByte & bits[i % 8]
          ? publicKey.subarray(i * 64 + 32, (i + 1) * 64) // Note that s1 not s0
          : publicKey.subarray(i * 64, i * 64 + 32); // s0

        const actualHashKeyFromSig = createHash('sha256').update(Buffer.from(s_i)).digest();

        if (0 !== actualHashKeyFromSig.compare(expectedPublicKey)) {
          return false;
        }
      }

      return true;
    },
  };
};

const Lamport = LamportSignature();

const { privateKey, publicKey } = Lamport.generateKeys();

// Alice sends a message to Bob with (message/sig)
const message = "hi";
const signature = Lamport.sign(message);

// Bob got the public key 
const bobsPublicKey = publicKey;
const verified = Lamport.verify(bobsPublicKey, message, signature);
console.log(`verified: ${verified}`);