Deep Dive: Lim-Lee and Small Subgroup Attacks in Discrete Logarithmic Cryptosystems, Relationship to Bitcoin, and Implementation on Google Colab

Abstract: This paper examines a class of cryptanalytic attacks on protocols based on the discrete logarithm problem (DLP), particularly on Diffie–Hellman key exchange. The focus is on small subgroup attacks and their generalization, the Lim-Lee attack (Lim-Lee, 1997). The mathematical foundation, exploitation mechanisms, security methods, and the impact of these concepts on modern cryptocurrency systems such as Bitcoin are analyzed.

1. Introduction to the Discrete Logarithm Problem

The security of many public-key cryptosystems, including the classical Diffie-Hellman (DH) protocol and Elliptic Curve Cryptography (ECC), is based on the computational difficulty of the Discrete Logarithm Problem (DLP).

In the multiplicative group of a finite field or in the group of points of an elliptic curve, the problem is formulated as follows: given a generator of the group $g$ and element $y = g^{x}$ , it is necessary to find a secret indicator (scalar) $x$ If the order of the group (the number of its elements) has a large prime divisor, the problem is considered unsolvable in polynomial time for classical computers.

2. Small Subgroup Attacks

Small Subgroup Confinement Attacks occur when a protocol uses a group $G$ , the order of which $N = | G |$ is not a prime number, but is a composite number that includes small prime factors $q_{i}$ .

By Lagrange’s theorem, the order of any subgroup divides the order of the group. If $N$ composite, in $G$ subgroups of smaller order equal to the divisors are guaranteed to exist $N$ In a small-subgroup attack, an attacker (e.g., an active MitM attacker or a malicious server) sends the victim an illegitimate public key that belongs to a small-subgroup. $q$ .

Mathematical model of the attack

Suppose Alice and Bob perform a Diffie-Hellman key exchange. Alice generates a secret key $a$ and calculates the public key $A = g^{a}$ The attacker (Eve) intercepts $A$ and sends Alice a fake element instead of Bob’s key $B^{'}$ , having a small order $q$ (that is $(B^{'})^{q} = 1$ ).

Alice computes the shared secret: $S = (B^{'})^{a}$ . Because the order $B^{'}$ equal $q$ , a common secret $S$ can only accept $q$ possible values, and is actually calculated as $S = (B^{'})^{a (\mod q)}$ .

Eva can try everything $q$ possible values (since $q$ little) and find $S$ Thus Eve learns the meaning $a (\mod q)$ — partial information about Alice’s secret key.

3. Lim-Lee Attack (Lim-Lee, 1997)

In 1997, Jongin Lim and Pil Joong Lee published a paper extending the concept of small-subgroup attacks to the case where the secret key is used multiple times (static Diffie-Hellman). Their attack allows one to recover the entire secret key using the Chinese Remainder Theorem (CRT).

Lima-Li attack algorithm

Parameter Analysis: The attacker analyzes the parameters of the cryptosystem and finds a decomposition of the order of the group $N$ (or the order of the subgroup used, if it is not prime) into factors: $N = q_{1} \cdot q_{2} \cdot . . . \cdot q_{k} \cdot R$ , Where $q_{i}$ — small prime numbers.
Sending elements of small order: For each small prime factor $q_{i}$ the attacker finds the element $y_{i}$ with order $q_{i}$ The attacker initiates $k$ sessions with the victim (or sends a composite element), substituting $y_{i}$ instead of the legitimate public key.
Partial Information Gathering: Victim figures out the shared secret $S_{i} = y_{i}^{x}$ By observing the protocol’s response (for example, if the secret is used for symmetric encryption or MAC verification), the attacker can brute-force $x_{i} = x (\mod q_{i})$ The enumeration takes $O (q_{i})$ time.
Key recovery: Having assembled a comparison system: $x \equiv x_{1} (\mod q_{1})$ $x \equiv x_{2} (\mod q_{2})$ $. . .$ $x \equiv x_{k} (\mod q_{k})$ The attacker uses the Chinese remainder theorem to calculate the value $x (\mod M)$ , Where $M = \prod_{i = 1}^{k} q_{i}$ . If $M > x$ , the key is fully recovered. Otherwise, the key search space is significantly reduced.

Historical example: The Lim-Lee attack exposed the vulnerability of many protocol implementations in the 1990s and 2000s that used parameters without checking that the group order had a large prime factor or without validating incoming public keys. This led to the standardization of “safe primes” of the form $p = 2 q + 1$ , Where $q$ also a prime number, and the introduction of a mandatory Subgroup Membership Test.

4. Relationship with Bitcoin and Elliptic Curve Cryptography

Bitcoin and most modern blockchains use elliptic curve cryptography, specifically the secp256k1 curve , for digital signatures (ECDSA/Schnorr) and address generation.

The equation of the curve secp256k1 over a finite field $F_{p}$ :

$y^{2} \equiv x^{3} + 7 (\mod p)$

Is Bitcoin susceptible to small subgroup attacks?

The key security parameter of an elliptic curve is the order of its base point $G$ , denoted as $n$ According to Hasse’s theorem, the number of points on the curve is close to the size of the field $p$ .

For secp256k1 the order of the point group is $n$ is a prime number (close to $2^{256}$ ). Cofactor $h$ , defined as the ratio of the total number of points on the curve to the order of the generator $n$ , is equal to 1:

$h = \frac{| E (F_{p}) |}{n} = 1$

Since the order of the group is prime and the cofactor is 1, there are no nontrivial subgroups on the curve secp256k1 . The order of any point on the curve (except the point at infinity) is $n$ Therefore, standard small subgroup attacks and the pure Lima-Lee attack are not applicable to Bitcoin .

This highlights a fundamental rule of cryptosystem design: using prime order groups is the best defense against Lim-Lee attacks.

Invalid Curve Attacks

While Bitcoin itself is secure, related protocols that interact with the blockchain (e.g. hardware wallets, multiparty computation (MPC) protocols, key exchange) may be vulnerable to Invalid Curve Attacks , which are mathematically related to small subset attacks.

If the implementation of point-scalar multiplication (for example, in a hardware wallet) accepts a point $P (x, y)$ from an external source, but does not check that the coordinates actually satisfy the curve equation $y^{2} = x^{3} + 7$ , an attacker can send a point lying on a different curve $y^{2} = x^{3} + 7^{'}$ , where the order of the group has small divisors. A wallet, using point addition formulas, which are often independent of the coefficient $b$ , will perform the calculation in the “weak” group, thereby leaking parts of the secret key (as in the Lima-Lee attack).

5. Protection, laws and regulations

To prevent attacks on small subgroups, cryptographic standards prescribe strict rules:

Safe Parameter Rule: Use groups whose order is a prime number (as in secp256k1) or has a large prime divisor (e.g., using safe primes $p = 2 q + 1$ in classic DH).
Subgroup Membership Test: When receiving a public key from another party, it is necessary to verify that it belongs to the correct subgroup.
In multiplicative DH: verify $1 < y < p - 1$ And $y^{q} \equiv 1 (\mod p)$ In
ECC: check that the coordinates of a point are not zero, the point satisfies the equation of the curve, and $n \cdot P = O$ (Where $O$ — a point at infinity).
Limiting Key Reuse: The Lima-Lee attack is effective against static keys. Using ephemeral keys (e.g., ECDHE) limits the ability to gather information across multiple sessions.

6. Examples of scripts on computer algebra systems

Below are conceptual examples of vulnerability and attack modeling in popular cryptanalysis frameworks.

Python (visual demo)

# Демонстрация концепции извлечения ключа через малую подгруппу
p = 23  # Малое простое поле
g = 2   # Генератор мультипликативной группы F_p* порядка p-1 = 22
# Порядок 22 составной: 22 = 2 * 11. Значит есть подгруппы порядка 2 и 11.

# Секретный ключ Алисы
x = 7
A = pow(g, x, p) # Легитимный публичный ключ

# Злоумышленник находит элемент порядка 2
# Элемент y = 22 (т.к. 22^2 mod 23 = 484 mod 23 = 1)
y_evil = 22

# Злоумышленник отправляет y_evil Алисе. Алиса вычисляет "общий секрет":
S = pow(y_evil, x, p)

# Злоумышленник знает, что порядок y_evil равен 2.
# Значит S = y_evil^(x mod 2)
# Если x четное, S = 1. Если x нечетное, S = 22.
print(f"Вычисленный Алисой секрет: {S}")
# Так как S = 22, злоумышленник узнает, что x mod 2 = 1.
# Часть ключа раскрыта!

SageMath (CRT application for Lima-Li)

# SageMath: Моделирование CRT для сборки ключа
# Предположим, злоумышленник собрал остатки ключа по малым модулям
q_list = [2, 3, 5, 7] # Малые порядки подгрупп
rem_list = [1, 2, 4, 3] # Полученные остатки (x mod q_i)

# Используем китайскую теорему об остатках (CRT)
x_recovered = crt(rem_list, q_list)
print("Восстановленная часть ключа (x mod 210):", x_recovered)
# Если секретный ключ x < 210, он восстановлен полностью.

Magma

// Magma: Проверка порядка группы и подгрупп
Z := IntegerRing();
p := 10009; // Простое поле, порядок группы p-1 = 10008
Factorization(p - 1);
// Результат: [ <2, 3>, <3, 2>, <139, 1> ]
// Группа имеет малые подгруппы порядков 2, 3, 4, 8, 9 и 139. Уязвима!

PARI/GP

\ PARI/GP: Поиск элемента малого порядка для атаки
p = 10009;
q = 139; \ Целевой малый порядок
g = 2; \ Базовый генератор группы порядка p-1
\ Создаем элемент порядка 139 возведением в степень (p-1)/139
y_evil = Mod(g, p)^((p-1)/q);
print(y_evil);
\ Проверяем порядок:
print(y_evil^q); \ Выведет Mod(1, 10009)

A deep analysis of the Lima-Lee attack and small subgroup attacks with practical demonstrations in Google Colab

This paper comprehensively examines small subgroup attacks and their generalization, the Lim-Lee attack (1997), in the context of protocols based on the discrete logarithm problem (DLP). The paper presents the mathematical foundations, exploitation mechanisms, and protection methods. Particular attention is paid to a practical demonstration of the attacks using Python scripts adapted for execution in the Google Colab environment. The applicability of these attacks to modern cryptocurrency systems, in particular Bitcoin, is also discussed, and the stability of the elliptic curve secp256k1 is analyzed. The security of many asymmetric cryptosystems (e.g., Diffie-Hellman, ElGamal, ECDSA) is based on the computational complexity of the discrete logarithm problem (DLP). In the multiplicative group of a finite field or in the group of points of an elliptic curve, the problem is formulated as follows: given a generator $g$ and element $y = g^{x}$ , find the indicator $x$ If the order of the group has a large prime divisor, the problem is considered unsolvable in polynomial time on classical computers.

However, in practice, the correctness of protocol implementation can be compromised due to incorrect parameter selection or lack of validation of input data. These are the errors exploited by attacks on small subgroups and their generalization, the Lima-Lee attack .

2. Mathematical foundations

Let $G$ – a finite Abelian group whose order $N = | G |$ composite. According to Lagrange’s theorem, the order of each subgroup divides $N$ . So, if $N$ has a small prime divisor $q$ , then in $G$ there is a subgroup of order $q$ .

DLP based protocols typically use a cyclic subgroup $⟨ g ⟩$ simple order $p$ (Where $p$ – a large simple one). But if the group is chosen incorrectly (for example, $N$ composite), or the attacker can slip in an element from a subgroup of low order, a leak of information about the secret key occurs.

3. Small Subgroup Attack

Let’s consider the classic Diffie-Hellman protocol. Alice and Bob want to develop a shared secret. Alice chooses the secret. $a$ , calculates $A = g^{a}$ and sends it to Bob. Eve, a malicious user, intercepts the message and replaces Bob’s public key with the element $B^{'}$ small order $q$ Alice calculates $S = (B^{'})^{a}$ . Because the order $B^{'}$ equal $q$ , meaning $S$ depends only on $a mod q$ . Eva is trying to find $q$ options are found $S$ and receives $a mod q$ Thus, part of the secret key is revealed.

Mathematical model: $S = (B^{'})^{a} = (B^{'})^{a mod q}$ The attacker goes through everything $r \in [0, q - 1]$ and checks if the calculated one matches $S$ with the real one (e.g. using known plaintext or MAC).

4. Lim-Lee Attack (Lim-Lee, 1997)

In 1997, Jeong In Lim and Pil Jung Lee proposed an extension of the attack to the case of multiple use of a static key (for example, in long-term key protocols). An attacker can conduct multiple sessions using elements of low order for different prime divisors. $q_{i}$ order of the group, and using the Chinese Remainder Theorem (CRT) to recover the secret key $x$ entirely (or significantly reduce the search space).

Lima-Li attack algorithm

Order factorization $N = q_{1}^{e_{1}} \dots q_{k}^{e_{k}} \cdot R$ , Where $q_{i}$ – small primes.
For everyone $q_{i}$ the attacker finds the element $y_{i}$ order $q_{i}$ (or $q_{i}^{e_{i}}$ ).
Conducts $k$ sessions, substituting $y_{i}$ instead of a legitimate public key. Receives the remainder $x_{i} = x mod q_{i}$ .
Using CRT calculates $x mod M$ , Where $M = \prod q_{i}$ . If $M > x$ , the key has been fully restored.

This attack is especially dangerous when the key is used multiple times (static DH) and the group order has many small divisors.

5. Example of a vulnerable system and protection

A classic example is a group $Z_{p}^{*}$ , Where $p - 1$ has small prime divisors. If developers use such $p$ without verification, the system is vulnerable. Protection:

Use safe primes such as $p = 2 q + 1$ , Where $q$ – is prime, then the order of the group has only divisors 2 and $q$ The subgroup of order 2 is easy to detect and does not provide much information.
Mandatory validation of public keys (checking membership in the main subgroup).
Use of ephemeral keys (Ephemeral Diffie‑Hellman, DHE/ECDHE).

6. Application to Bitcoin and Elliptic Curve Cryptography

Bitcoin uses the elliptic curve secp256k1 over $F_{p}$ , Where $p = 2^{256} - 2^{32} - 977$ . Base point $G$ has a simple order $n$ (cofactor $h = 1$ ).

Since the order of the group is prime, nontrivial subgroups do not exist, and pure small subgroup attacks are inapplicable to Bitcoin. However, related protocols (e.g., hardware wallets, MPC) may be vulnerable to invalid curve attacks , where an attacker substitutes a point lying on another curve with small order divisors, thereby obtaining partial information about the scalar.

7. Hands-on demos in Google Colab

Below are ready-made Python scripts that can be run in Google Colab to demonstrate attacks. They use only standard libraries ( sympy, random, math). For working with elliptic curves, a simple implementation or library is used tinyec (available through pip install tinyec).

7.1. Installing required libraries

!pip install sympy tinyec

7.2. Demonstration of an attack on a small subgroup in $Z_{p}^{*}$

In this example, we create a simple field with composite multiplicative group order, find the element of order 2, and show the leakage of a secret bit.

import random
from sympy import primitive_root, factorint

# Выбираем простое p, где p-1 имеет маленький делитель (например, 2)
p = 23  # p-1 = 22 = 2 * 11
g = primitive_root(p)  # находим первообразный корень

# Секретный ключ Алисы (пусть будет случайным)
x = random.randint(1, p-2)
print(f"Секретный ключ Алисы: x = {x}")

# Легитимный открытый ключ
A = pow(g, x, p)
print(f"Открытый ключ Алисы: A = {A}")

# Злоумышленник выбирает элемент порядка 2 (он равен p-1)
y_evil = p - 1  # (p-1)^2 ≡ 1 mod p

# Алиса вычисляет общий секрет с поддельным ключом
S = pow(y_evil, x, p)

# Перебором определяем x mod 2
if S == 1:
    print("x mod 2 = 0 (чётное)")
else:
    print("x mod 2 = 1 (нечётное)")

print(f"Реальный x mod 2 = {x % 2}")

7.3. Key recovery using CRT (Lima-Lee attack)

Let’s assume the attacker has collected the remainders of small modules. We use sympy.ntheory.modular.crt.

from sympy.ntheory.modular import crt

# Собранные остатки
moduli = [2, 3, 5, 7]      # малые делители порядка
remainders = [1, 2, 4, 3]  # x mod q_i (получены из атак)

# CRT
x_recovered, modulus = crt(moduli, remainders)
print(f"Восстановленное значение x (mod {modulus}): {x_recovered}")

# Если реальный x меньше modulus, он восстановлен полностью
real_x = 123  # пример
if real_x < modulus:
    print(f"Полный ключ: {x_recovered} (совпадает с {real_x})")
else:
    print(f"Пространство поиска сокращено до {modulus} вариантов")

7.4 Checking the order of a group and finding elements of small order

from sympy import factorint, is_primitive_root

p = 10009
order = p - 1
print(f"Порядок группы: {order}")
print("Разложение на множители:", factorint(order))

# Проверим, есть ли малые делители
small_primes = [q for q in factorint(order).keys() if q < 100]
if small_primes:
    print(f"Есть малые простые делители: {small_primes}")
    # Найдём элемент порядка q (например, q=2)
    q = small_primes[0]
    # Возьмём генератор g = primitive_root(p)
    g = 2  # упрощённо, для демонстрации
    y_evil = pow(g, order // q, p)
    print(f"Элемент порядка {q}: {y_evil}")
    print(f"Проверка: {y_evil}^{q} mod p = {pow(y_evil, q, p)}")
else:
    print("Малых делителей нет (безопасная группа)")

7.5. Invalid Curve Attack on an Elliptic Curve (Conceptual Example)

To demonstrate, let’s create two curves above $F_{23}$ : legitimate $y^{2} = x^{3} + x + 1$ and invalid $y^{2} = x^{3} + x + 2$ , where the second order has small divisors. We will show how substituting a point with an invalid curve can reveal the bits of a scalar.

# Упрощённая реализация операций на эллиптической кривой
# (для образовательных целей)
import random

def is_on_curve(x, y, a, b, p):
    return (y*y - (x*x*x + a*x + b)) % p == 0

# Параметры p=23, кривая 1: y^2 = x^3 + x + 1 (легитимная)
p = 23
a1, b1 = 1, 1
# Кривая 2: y^2 = x^3 + x + 2 (невалидная, но имеющая малый порядок)
a2, b2 = 1, 2

# Точка на невалидной кривой с малым порядком (найдём перебором)
# Для простоты возьмём готовую точку (для p=23, b=2 есть точка порядка 3)
x_evil, y_evil = 7, 8  # проверьте, что на второй кривой
assert is_on_curve(x_evil, y_evil, a2, b2, p)

# Пусть секретный скаляр Алисы
x_secret = 7

# Легитимное умножение на скаляр (без проверки принадлежности кривой)
# Реализуем сложение и удвоение (примитивно)
def point_add(P, Q, a, p):
    if P is None:
        return Q
    if Q is None:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None
    if x1 == x2 and y1 == y2:
        # удвоение
        lam = (3*x1*x1 + a) * pow(2*y1, -1, p) % p
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (lam*lam - x1 - x2) % p
    y3 = (lam*(x1 - x3) - y1) % p
    return (x3, y3)

def scalar_mult(k, P, a, p):
    R = None
    Q = P
    while k:
        if k & 1:
            R = point_add(R, Q, a, p)
        Q = point_add(Q, Q, a, p)
        k >>= 1
    return R

# Алиса получает злую точку и вычисляет "общий секрет" (результат умножения)
S = scalar_mult(x_secret, (x_evil, y_evil), a1, p)  # Используем коэффициенты легитимной кривой!

# Злоумышленник знает, что порядок точки на невалидной кривой равен q=3
# и может перебрать возможные значения S (их всего 3)
# Если S совпадает с одним из них, он узнаёт x_secret mod q
print(f"Результат умножения: {S}")
# Перебор всех возможных x mod 3
for r in range(3):
    test = scalar_mult(r, (x_evil, y_evil), a1, p)
    if test == S:
        print(f"Найдено x mod 3 = {r}")
        break

In practice, invalid curve attacks require more careful selection of parameters, but the example given illustrates the basic idea.

7.6 Checking the order of a point on an elliptic curve secp256k1 (demonstration)

We use the library tinyec to work with secp256k1 and verify that the order of point G is a large prime number.

from tinyec import registry
import sympy

# Загружаем кривую secp256k1
curve = registry.get_curve('secp256k1')
G = curve.g
n = curve.field.n  # порядок группы
print(f"Порядок базовой точки: {n}")
print(f"Прост ли порядок? {sympy.isprime(n)}")
print(f"Кофактор: {curve.field.h}")

# Проверим, что n*G = точка в бесконечности
inf = scalar_mult(n, (G.x, G.y), curve.a, curve.field.p)  # если бы мы реализовали
# Но проще: tinyec уже имеет метод
print(f"n*G == inf? {n * G == None}")  # tinyec использует None для inf

8. Protection methods and recommendations

To prevent the attacks described, the following rules must be observed:

Parameter selection: use groups of prime order or with cofactor equal to 1 (such as secp256k1). In the case of a multiplicative group, use secure primes.
Validation of input points/keys: checking membership in the correct subgroup (Subgroup Membership Test). For ECC, this is a check that $P$ lies on the curve and $n \cdot P = O$ .
Limit key reuse: Use ephemeral keys to prevent an attacker from collecting enough CRT balances.
Continuous implementation testing: testing for resistance to invalid curve attacks.

Conclusion

The Lima-Lee attack and small subgroup attacks are classic examples of how mathematical properties of groups can be exploited to compromise key confidentiality. While modern standards (such as the use of prime-order curves) make these attacks irrelevant for many systems, they are important to keep in mind when designing new protocols and implementing cryptographic operations. The presented Google Colab scripts provide a clear demonstration of the attack mechanisms and reinforce the need for strict data validation. Small subgroup attacks and the Lima-Lee attack demonstrate the critical importance of proper parameter selection and input validation in public-key cryptosystems. While modern systems, such as Bitcoin with its prime-order secp256k1 curve, are structurally secure against these vulnerabilities, related implementations and adjacent protocols require ongoing enforcement of mathematical cryptographic laws (in particular, the Subgroup Membership Test and curve verification) to prevent secret material from leaking through mathematical backdoors.

Keywords: discrete logarithm, small subgroup, Lima-Li attack, Chinese remainder theorem, cryptanalysis, Bitcoin, secp256k1, invalid curve attack.

1. Introduction to the Discrete Logarithm Problem

2. Small Subgroup Attacks

Mathematical model of the attack

3. Lim-Lee Attack (Lim-Lee, 1997)

Lima-Li attack algorithm

4. Relationship with Bitcoin and Elliptic Curve Cryptography

Is Bitcoin susceptible to small subgroup attacks?

Invalid Curve Attacks

5. Protection, laws and regulations

6. Examples of scripts on computer algebra systems

Python (visual demo)

SageMath (CRT application for Lima-Li)

Magma

PARI/GP

A deep analysis of the Lima-Lee attack and small subgroup attacks with practical demonstrations in Google Colab

2. Mathematical foundations

3. Small Subgroup Attack

4. Lim-Lee Attack (Lim-Lee, 1997)

Lima-Li attack algorithm

5. Example of a vulnerable system and protection

6. Application to Bitcoin and Elliptic Curve Cryptography

7. Hands-on demos in Google Colab

7.1. Installing required libraries

7.2. Demonstration of an attack on a small subgroup in Zp∗

7.3. Key recovery using CRT (Lima-Lee attack)

7.4 Checking the order of a group and finding elements of small order

7.5. Invalid Curve Attack on an Elliptic Curve (Conceptual Example)

7.6 Checking the order of a point on an elliptic curve secp256k1 (demonstration)

8. Protection methods and recommendations

Conclusion

7.2. Demonstration of an attack on a small subgroup in $Z_{p}^{*}$