challenge: do challenge 42HEADv0.42.0master

1 files changed, 113 insertions, 0 deletions

diff --git a/challenge/c42.go b/challenge/c42.go
new file mode 100644
index 0000000..d3b1712
--- /dev/null
+++ b/challenge/c42.go
@@ -0,0 +1,113 @@
+// Copyright © 2025 siddharth ravikumar <s@ricketyspace.net>
+// SPDX-License-Identifier: ISC
+
+package challenge
+
+import (
+	"fmt"
+	"math/big"
+	"time"
+
+	"ricketyspace.net/cryptopals/lib"
+)
+
+func C42() {
+	var (
+		m    []byte
+		s    []byte
+		kp   *lib.RSAPair
+		sigm []byte
+		err  error
+	)
+
+	// Set message.
+	m = []byte("hi mom")
+
+	// Generate 1024 bit key pair.
+	kp, err = lib.RSAGenKey(1024)
+	if err != nil {
+		fmt.Printf("gen key: %v\n", err)
+		return
+	}
+
+	// Verify RSA signing works.
+	s, err = kp.Private.Sign(m)
+	if err != nil {
+		fmt.Printf("sign: %v\n", err)
+		return
+	}
+	if !kp.Public.LazyVerify(m, s) {
+		fmt.Printf("sig check failed\n")
+	}
+
+	// Make message that will be given as input to create the RSA
+	// signature.
+	sigm, err = mkSigMsg(m, kp.Public)
+	if err != nil {
+		fmt.Printf("mk sig msg: %v\n", err)
+		return
+	}
+
+	var (
+		found   = false
+		tries   = 0
+		rn      = byte(0)
+		rnIdx   = len(sigm)
+		forgeds []byte // Forged signature.
+		el      time.Time
+	)
+	el = time.Now()
+	defer func() {
+		fmt.Printf(
+			"time to find forged signature: %v\n",
+			time.Since(el),
+		)
+	}()
+	sigm = append(sigm, rn)
+	for tries < 1000000 {
+		forgeds = lib.BigIntCubeRoot(
+			new(big.Int).SetBytes(sigm),
+		).Bytes()
+		if forgeds != nil {
+			var ok = kp.Public.LazyVerify(m, forgeds)
+			if ok {
+				found = true
+				break
+			}
+		}
+		tries += 1
+
+		if rn == 255 {
+			rn = 0
+			rnIdx += 1
+			sigm = append(sigm, rn)
+		} else {
+			rn += 1
+		}
+		sigm[rnIdx] = rn
+
+	}
+	if found {
+		fmt.Printf("found forged signature: %v\n", forgeds)
+	} else {
+		fmt.Printf("unable to find forged signature\n")
+	}
+}
+
+func mkSigMsg(msg []byte, pub *lib.RSAPub) (m []byte, err error) {
+	var (
+		dgst lib.Md4
+		d    []byte // Data to sign.
+		eb   []byte
+	)
+	dgst.Init([]uint32{})
+	dgst.Message(msg)
+	d = dgst.Hash()
+
+	// Build encryption block.
+	eb = []byte{0x00, 0x01, 0xFF, 0xFF, 0x00}
+	eb = append(eb, d...)
+
+	m = eb
+	return
+}