feat(app): CTF RSA-crack支持多因子费马分解, 修复fullFermat错误后停止分解

java66liu · Jan 24, 2023 · ab347f4 · ab347f4
1 parent 702ba10
commit ab347f4
Show file tree

Hide file tree

Showing 3 changed files with 64 additions and 3 deletions.
diff --git a/app/src/main/kotlin/me/leon/ctf/rsa/Factors.kt b/app/src/main/kotlin/me/leon/ctf/rsa/Factors.kt
@@ -70,11 +70,61 @@ fun BigInteger.fermat(timeOut: Int = TIME_OUT): MutableList<BigInteger> {
     return mutableListOf(this.negate())
 }
 
+/** 适用因子相差较小 时间复杂度 O(|p-q|) */
+fun BigInteger.fermatMore(
+    num: Int = 2,
+    timeOut: Int = TIME_OUT
+): MutableSet<Pair<BigInteger, BigInteger>> {
+    val result = mutableSetOf<Pair<BigInteger, BigInteger>>()
+    with(sqrtAndRemainder()) {
+        if (this.last() != ZERO) {
+            var a = first() + ONE
+            var count = 0
+            var b: BigInteger
+            val startTime = System.currentTimeMillis()
+
+            while (System.currentTimeMillis() - startTime < timeOut) {
+                val b1 = a.pow(2) - this@fermatMore
+                b = b1.sqrt()
+                count++
+                if (b * b == b1) {
+                    println("solved iteration $count \n\tp = ${a + b} \n\tq= ${a - b}\n")
+                    result.add((a + b) to (a - b))
+                    if (result.size == num) {
+                        return result
+                    }
+                }
+                a++
+            }
+        }
+    }
+    if (result.size == 0) {
+        println("no fermat solution")
+    }
+    return result
+}
+
 fun BigInteger.fullFermat(timeOut: Int = TIME_OUT): List<BigInteger> {
     if (isProbablePrime(100)) return listOf(this)
-    return fermat(timeOut)
-        .map { it.fullFermat(timeOut).takeIf { it.size > 1 } ?: listOf(it) }
-        .flatten()
+    return runCatching {
+            fermat(timeOut)
+                .map { it.fullFermat(timeOut).takeIf { it.size > 1 } ?: listOf(it) }
+                .flatten()
+        }
+        .getOrDefault(listOf(this.negate()))
+}
+
+fun BigInteger.fullFermat2(timeOut: Int = TIME_OUT): List<BigInteger> {
+    println("full $this")
+    if (isProbablePrime(100)) return listOf(this)
+    val fermatMore = fermatMore(timeOut)
+    return if (fermatMore.size >= 2) {
+        val (p1q1, p2q2) = fermatMore.toList()[0]
+        val (p1q2, p2q1) = fermatMore.toList()[1]
+        mutableListOf(p1q1.gcd(p1q2), p2q2.gcd(p2q1), p1q1.gcd(p2q1), p2q2.gcd(p1q2))
+    } else {
+        listOf(this.negate())
+    }
 }
 
 fun BigInteger.pollardsRhoFactors(
@@ -174,6 +224,10 @@ fun BigInteger.factor(): MutableList<BigInteger> {
                 println("---div--- $it")
                 it.trialDivide()
             },
+            {
+                println("---fermat2---")
+                it.fullFermat2(TIME_OUT)
+            },
             {
                 println("---factorDb---")
                 it.factorDb()

diff --git a/app/src/test/kotlin/me/leon/math/factor/FactorTest.kt b/app/src/test/kotlin/me/leon/math/factor/FactorTest.kt
@@ -94,6 +94,10 @@ class FactorTest {
             println("____${it.size}")
             println(it.joinToString("\n"))
         }
+
+        params = "rsa_nec_fermat_4.txt".parseRsaParams()
+        val fermatMore = requireNotNull(params["n"]).factor()
+        assertEquals(4, fermatMore.size)
     }
 
     @Test

diff --git a/testdata/ctf/rsa/rsa_nec_fermat_4.txt b/testdata/ctf/rsa/rsa_nec_fermat_4.txt
@@ -0,0 +1,3 @@
+n = 32481415283829255738340971974996440308678927230347135108620374939715138530763511922162670183907243606574444169915409791604348383760619870966025875897723568019791384873824917630615306169399783499416450554084947937964622799112489092007113967359069561646966430880857626323529067736582503070705981530002918845439
+e = 65537
+c = 13000287388412632836037240605681731720629565122285665653580432791960428695510699983959843546876647788034949392762752577597448919397451077080119543495058705350347758604475392673242110787093172219487592930482799866421316089027633497253411081184454114601840835490688775466505809830410778091437211186254631834255