31_ECDLP/ECDLP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "04791372",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7, 8)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sympy import mod_inverse\n",
    "\n",
    "# 重新定义椭圆曲线参数和点P\n",
    "p = 13\n",
    "a = -1\n",
    "b = 1\n",
    "P = (0, 1)\n",
    "\n",
    "# 定义椭圆曲线上的点加法和点翻倍操作\n",
    "# 定义加法运算\n",
    "def elliptic_curve_addition(P, Q, a, p):\n",
    "    if P == ('inf', 'inf'):\n",
    "        return Q\n",
    "    if Q == ('inf', 'inf'):\n",
    "        return P\n",
    "    if P[0] == Q[0] and (P[1] != Q[1] or P[1] == 0):\n",
    "        # P + Q = O (无穷远点) 如果它们是垂直对称的点或P是切点\n",
    "        return ('inf', 'inf')\n",
    "    if P == Q:\n",
    "        # 点翻倍\n",
    "        lambda_ = (3 * P[0]**2 + a) * mod_inverse(2 * P[1], p) % p\n",
    "    else:\n",
    "        # 点加法\n",
    "        lambda_ = (Q[1] - P[1]) * mod_inverse(Q[0] - P[0], p) % p\n",
    "\n",
    "    x3 = (lambda_**2 - P[0] - Q[0]) % p\n",
    "    y3 = (lambda_ * (P[0] - x3) - P[1]) % p\n",
    "\n",
    "    return (x3, y3)\n",
    "\n",
    "def ecc_double_and_add(P, k, a, p):\n",
    "    \"\"\"Double-And-Add algorithm for scalar multiplication on elliptic curves.\"\"\"\n",
    "    result = ('inf', 'inf')  # 无穷远点\n",
    "    addend = P\n",
    "\n",
    "    while k:\n",
    "        if k & 1:\n",
    "            result = elliptic_curve_addition(result, addend, a, p)\n",
    "        addend = elliptic_curve_addition(addend, addend, a, p)\n",
    "        k >>= 1\n",
    "    return result\n",
    "\n",
    "# 测试Double-And-Add算法\n",
    "# 选择一个标量k = 9进行标量乘法测试\n",
    "k = 9\n",
    "result = ecc_double_and_add(P, k, a, p)\n",
    "\n",
    "result\n",
    "# (7, 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "a3a9123c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "点 P 的阶是: 19\n"
     ]
    }
   ],
   "source": [
    "# 计算点的阶\n",
    "def find_order_of_point(P, a, p):\n",
    "    S = P\n",
    "    n = 1\n",
    "    while S != ('inf', 'inf'):  # ('inf', 'inf') 是无穷远点\n",
    "        S = elliptic_curve_addition(S, P, a, p)\n",
    "        n += 1\n",
    "    return n\n",
    "\n",
    "# 计算点P的阶\n",
    "order = find_order_of_point(P, a, p)\n",
    "print(f\"点 P 的阶是: {order}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "4cd0319a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Private Key: 123456789\n",
      "Public Key: (4051293998585674784991639592782214972820158391371785981004352359465450369227, 88166831356626186178414913298033275054086243781277878360288998796587140930350)\n"
     ]
    }
   ],
   "source": [
    "# 椭圆曲线 secp256k1 示例\n",
    "# 利用标量乘法，从私钥生成公钥\n",
    "from py_ecc.secp256k1 import secp256k1\n",
    "\n",
    "def generate_public_key(private_key):\n",
    "    \"\"\"\n",
    "    使用secp256k1椭圆曲线，根据给定的私钥生成公钥。\n",
    "    \n",
    "    参数:\n",
    "    private_key (int): 私钥，一个大整数。\n",
    "    \n",
    "    返回:\n",
    "    (int, int): 公钥，椭圆曲线上的点。\n",
    "    \"\"\"\n",
    "    # secp256k1的基点\n",
    "    G = secp256k1.G\n",
    "    \n",
    "    # 计算公钥\n",
    "    public_key = secp256k1.multiply(G, private_key)\n",
    "    \n",
    "    return public_key\n",
    "\n",
    "# 示例：使用一个随机的私钥\n",
    "private_key = 123456789  # 在实际应用中，私钥应该是随机生成的大整数，比如 private_key = int(os.urandom(32).hex(), 16)\n",
    "\n",
    "# 生成公钥\n",
    "public_key = generate_public_key(private_key)\n",
    "\n",
    "# 打印结果\n",
    "print(f\"Private Key: {private_key}\")\n",
    "print(f\"Public Key: {public_key}\")\n",
    "\n",
    "# 输出\n",
    "# Private Key: 123456789\n",
    "# Public Key: (4051293998585674784991639592782214972820158391371785981004352359465450369227, 88166831356626186178414913298033275054086243781277878360288998796587140930350)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27df043e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}