summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--challenge/c40.go82
-rw-r--r--cryptopals.go2
2 files changed, 84 insertions, 0 deletions
diff --git a/challenge/c40.go b/challenge/c40.go
new file mode 100644
index 0000000..ec16059
--- /dev/null
+++ b/challenge/c40.go
@@ -0,0 +1,82 @@
+// Copyright © 2022 siddharth ravikumar <s@ricketyspace.net>
+// SPDX-License-Identifier: ISC
+
+package challenge
+
+import (
+ "fmt"
+ "math/big"
+
+ "ricketyspace.net/cryptopals/lib"
+)
+
+func C40() {
+ msg := []byte("42 is the answer.")
+
+ // Generate 3 rsa key pairs and capture the their public keys.
+ var rsaPubs []*lib.RSAPub
+ for i := 0; i < 3; i++ {
+ rsa, err := lib.RSAGenKey()
+ if err != nil {
+ fmt.Printf("gen key failed: %v", err)
+ return
+ }
+ rsaPubs = append(rsaPubs, rsa.Public)
+ }
+
+ // Encrypt message with the 3 rsa public keys.
+ var ciphers [][]byte
+ for i := 0; i < 3; i++ {
+ enc := rsaPubs[i].Encrypt(msg)
+ if len(enc) < 1 {
+ fmt.Printf("encrypt failed: %v", enc)
+ return
+ }
+ ciphers = append(ciphers, enc)
+ }
+
+ // Compute m_s_n
+ var msn []*big.Int
+ for i := 0; i < 3; i++ {
+ msn = append(msn, big.NewInt(0).Mul(
+ rsaPubs[(i+1)%3].N(), rsaPubs[(i+2)%3].N(),
+ ))
+ }
+
+ // Compute N_012
+ n012 := big.NewInt(1)
+ for _, rpub := range rsaPubs {
+ n012 = n012.Mul(n012, rpub.N())
+ }
+
+ // Compute combination of residues.
+ result := big.NewInt(0)
+ for i := 0; i < 3; i++ {
+ r := big.NewInt(0).Mul(
+ big.NewInt(0).SetBytes(ciphers[i]),
+ msn[i],
+ ) // c_i * m_s_i
+
+ // invmod(m_s_i, n_i)
+ im, err := lib.InvMod(msn[i], rsaPubs[i].N())
+ if err != nil {
+ fmt.Printf("invmod: invmod(m_s_%d, n_%d): %v",
+ i, i, err,
+ )
+ return
+ }
+
+ // c_i * m_s_i * invmod(m_s_i, n_i)
+ r = r.Mul(r, im)
+
+ // Add to result.
+ result.Add(result, r)
+ }
+
+ // result mod N_012
+ result = result.Mod(result, n012)
+
+ // Cube root the result.
+ deci := lib.BigIntCubeRoot(result)
+ fmt.Printf("Decrypted message: %s\n", deci.Bytes())
+}
diff --git a/cryptopals.go b/cryptopals.go
index 8ff0d6c..0452433 100644
--- a/cryptopals.go
+++ b/cryptopals.go
@@ -98,5 +98,7 @@ func main() {
challenge.C38(flag.Args())
case 39:
challenge.C39()
+ case 40:
+ challenge.C40()
}
}