信息计算2019级1班19号谭斌斌

谭斌斌 · 发表于 2022-5-2 17:20:09

本帖最后由谭斌斌于 2022-5-2 17:21 编辑

大数RSA算法的实现

一、源码

工具类代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Security_Test3
{
class RSATools
{
public static bool isPrim(long num)
{
if (num == 2 || num == 3)
return true;
if (num % 6 != 1 && num % 6 != 5)
return false;
long tmp = (long)Math.Sqrt(num);
for (long i = 5; i <= tmp; i += 6)
if (num % i == 0 || num % (i + 2) == 0)
return false;
return true;
}
public static long gcd(long x, long y) => y != 0 ? gcd(y, x % y) : x;
public static long inverse(long number1, long number3)
{
long x1 = 1, x2 = 0, x3 = number3, y1 = 0, y2 = 1, y3 = number1;
long q;
long number4 = 0;
long t1, t2, t3;
while (y3 != 0)
{
if (y3 == 1)
{
number4 = y2;
break;
}
else
{
q = (x3 / y3);
t1 = x1 - q * y1;
t2 = x2 - q * y2;
t3 = x3 - q * y3;
x1 = y1; x2 = y2; x3 = y3;
y1 = t1; y2 = t2; y3 = t3;
}
}
if (number4 < 0)
number4 = number4 + number3;
return number4;
}
public static long getMod(long a, long b, long c)
//利用快速指数模运算，计算m^e mod n
{
long number3 = 1;
while (a != 0)
{
if (a % 2 == 1)
{
a = a - 1;
number3 = (number3 * b) % c;
}
else
{
a = (a / 2);
b = (b * b) % c;
}
}
return number3;
}
public static long getN(long p, long q) => p * q;
public static long getEuler_N(long p, long q) => (p - 1) * (q - 1);
public static void getP_Q(out long p, out long q)
{
Random random = new Random();
while (true)
{
p = random.Next(1000);
q = random.Next(2000);
if (isPrim(p) && isPrim(q)) return;
}
}
public static byte[] longToBytes(long a)
{
byte[] b = new byte[8];
b[0] = (byte)(a);
b[1] = (byte)(a >> 8 & 0xFF);
b[2] = (byte)(a >> 16 & 0xFF);
b[3] = (byte)(a >> 24 & 0xFF);
b[4] = (byte)(a >> 32 & 0xFF);
b[5] = (byte)(a >> 40 & 0xFF);
b[6] = (byte)(a >> 48 & 0xFF);
b[7] = (byte)(a >> 56 & 0xFF);
return b;
}
public static long BytesToLong(byte[] input)
{
uint num = (uint)(((input[0] | (input[1] << 8)) | (input[2] << 0x10)) | (input[3] << 0x18));
uint num2 = (uint)(((input[4] | (input[5] << 8)) | (input[6] << 0x10)) | (input[7] << 0x18));
return (long)((num2 << 0x20) | num);
}
public static long[] UTF8ToLong(string input)
{
string input_64 = Convert.ToBase64String(Encoding.UTF8.GetBytes(input));
byte[] inputByte = Convert.FromBase64String(input_64);
long[] inputLong = new long[inputByte.Length];
for (int i = 0; i < inputByte.Length; i++)
{
inputLong[i] = (long)inputByte[i];
}
return inputLong;
}
public static string longToUTF8(long[] input)
{
byte[] inputByte = new byte[input.Length];
for (int i = 0; i < inputByte.Length; i++)
{
inputByte[i] = (byte)input[i];
}
string inputBase64 = Convert.ToBase64String(inputByte);
byte[] outputb = Convert.FromBase64String(inputBase64);
string output = Encoding.UTF8.GetString(outputb);
return output;
}
public static long[] Base64ToLong(string input)
{
List<long> output_l = new List<long>();
string t = "";
for (int i = 0; i < input.Length; i++)
{
t += input[i];
if (input[i] == '=')
{
byte[] tByte = Convert.FromBase64String(t);
output_l.Add(BytesToLong(tByte));
t = "";
}
}
return output_l.ToArray(); ;
}
public static string longToBase64(long[] input)
{
byte[][] inputByte = new byte[input.Length][];
string output = "";
for (int i = 0; i < input.Length; i++)
{
inputByte[i] = longToBytes(input[i]);
output += Convert.ToBase64String(inputByte[i]);
}
return output;
}
}
}

复制代码

RSA算法代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Security_Test3
{
class RSA
{
private long p, q;
private long n;
private long euler_N;
private long[] publicKey;//0-e 1-n
private long[] privateKey;//0-d 1-n
public long P { get => p; set => p = value; }
public long Q { get => q; set => q = value; }
public long[] PublicKey { get => publicKey; set => publicKey = value; }
public long[] PrivateKey { get => privateKey; set => privateKey = value; }
public long N { get => n; set => n = value; }
public long Euler_N { get => euler_N; set => euler_N = value; }
public void InitPublicKey()
//初始化公钥
{
RSATools.getP_Q(out p, out q);
euler_N = RSATools.getEuler_N(p, q);
long e;
n = RSATools.getN(p, q);
Random radom = new Random();
while (true)
{
e = radom.Next(655300);
if (e > 1 && e < euler_N && RSATools.gcd(e, euler_N) == 1 && RSATools.isPrim(e)) break;
}
publicKey = new long[2];
publicKey[0] = e;
publicKey[1] = n;
}
public void InitPrivateKey()
//初始化私钥
{
long d = RSATools.inverse(publicKey[0], euler_N);
privateKey = new long[2];
privateKey[0] = d;
privateKey[1] = n;
}
//加密操作
public long encrypt(long plaintext, long[] p_k) => RSATools.getMod(p_k[0], plaintext, p_k[1]);
//解密操作
public long decrypt(long ciphertext) => RSATools.getMod(privateKey[0], ciphertext, privateKey[1]);
public string getCiphertext(string plaintext, long[] p_k)
//加密明文得到密文
{
long[] p_long = RSATools.UTF8ToLong(plaintext);
long[] c_long = new long[p_long.Length];
for (int i = 0; i < p_long.Length; i++)
{
c_long[i] = encrypt(p_long[i], p_k);
}
string c_text = RSATools.longToBase64(c_long);
return c_text;
}
public string getPlaintext(string ciphertext)
//解密密文得到明文
{
long[] c_long = RSATools.Base64ToLong(ciphertext);
long[] p_long = new long[c_long.Length];
for (int i = 0; i < c_long.Length; i++)
{
p_long[i] = decrypt(c_long[i]);
}
string p_text = RSATools.longToUTF8(p_long);
return p_text;
}
}
}

复制代码

主函数代码：

using System;
namespace Security_Test3
{
class Program
{
static void Main(string[] args)
{
RSA a = new RSA();
a.InitPublicKey();
a.InitPrivateKey();
string p = a.P.ToString();
string q = a.Q.ToString();
string publickey = a.PublicKey[0].ToString() + "-" + a.PublicKey[1].ToString();
Console.WriteLine("明文为：");
string plaintext = "于是二子愀然改容，超若自失，逡巡避席，曰：“鄙人固陋，不知忌讳，乃今日见教，谨受命矣。”";
Console.WriteLine(plaintext);
Console.WriteLine();
//Console.WriteLine("p:"+p+";q:"+q);
Console.Write("公钥为：");
Console.WriteLine(publickey);
Console.WriteLine();
Console.WriteLine("密文为：");
string ciphertext = a.getCiphertext(plaintext, a.PublicKey);
Console.WriteLine(ciphertext);
Console.WriteLine();
Console.WriteLine("解密后的明文为：");
string decryptedtext = a.getPlaintext(ciphertext);
Console.WriteLine(decryptedtext);
}
}
}

复制代码

谭斌斌 · 发表于 2022-5-2 17:20:53

二、运行截图

谭斌斌 · 发表于 2022-6-3 00:16:08

ECC源码：

def get_inverse(mu, p):
"""
获取y的负元
"""
for i in range(1, p):
if (i*mu)%p == 1:
return i
return -1
def get_gcd(zi, mu):
"""
获取最大公约数
"""
if mu:
return get_gcd(mu, zi%mu)
else:
return zi
def get_np(x1, y1, x2, y2, a, p):
"""
获取n*p，每次+p，直到求解阶数np=-p
"""
flag = 1 # 定义符号位（+/-）
# 如果 p=q k=(3x2+a)/2y1mod p
if x1 == x2 and y1 == y2:
zi = 3 * (x1 ** 2) + a # 计算分子【求导】
mu = 2 * y1 # 计算分母
# 若P≠Q，则k=(y2-y1)/(x2-x1) mod p
else:
zi = y2 - y1
mu = x2 - x1
if zi* mu < 0:
flag = 0 # 符号0为-（负数）
zi = abs(zi)
mu = abs(mu)
# 将分子和分母化为最简
gcd_value = get_gcd(zi, mu) # 最大公約數
zi = zi // gcd_value # 整除
mu = mu // gcd_value
# 求分母的逆元逆元： ∀a ∈G ，ョb∈G 使得 ab = ba = e
# P(x,y)的负元是 (x,-y mod p)= (x,p-y) ，有P+(-P)= O∞
inverse_value = get_inverse(mu, p)
k = (zi * inverse_value)
if flag == 0: # 斜率负数 flag==0
k = -k
k = k % p
# 计算x3,y3 P+Q
"""
x3≡k2-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)
"""
x3 = (k ** 2 - x1 - x2) % p
y3 = (k * (x1 - x3) - y1) % p
return x3,y3
def get_rank(x0, y0, a, b, p):
"""
获取椭圆曲线的阶
"""
x1 = x0 #-p的x坐标
y1 = (-1*y0)%p #-p的y坐标
tempX = x0
tempY = y0
n = 1
while True:
n += 1
# 求p+q的和，得到n*p，直到求出阶
p_x,p_y = get_np(tempX, tempY, x0, y0, a, p)
# 如果 == -p,那么阶数+1，返回
if p_x == x1 and p_y == y1:
return n+1
tempX = p_x
tempY = p_y
def get_param(x0, a, b, p):
"""
计算p与-p
"""
y0 = -1
for i in range(p):
# 满足取模约束条件，椭圆曲线Ep(a,b)，p为质数，x,y∈[0,p-1]
if i**2%p == (x0**3 + a*x0 + b)%p:
y0 = i
break
# 如果y0没有，返回false
if y0 == -1:
return False
# 计算-y（负数取模）
x1 = x0
y1 = (-1*y0) % p
return x0,y0,x1,y1
def get_graph(a, b, p):
"""
输出椭圆曲线散点图
"""
x_y = []
# 初始化二维数组
for i in range(p):
x_y.append(['-' for i in range(p)])
for i in range(p):
val =get_param(i, a, b, p) # 椭圆曲线上的点
if(val != False):
x0,y0,x1,y1 = val
x_y[x0][y0] = 1
x_y[x1][y1] = 1
print("椭圆曲线的散列图为：")
for i in range(p): # i= 0-> p-1
temp = p-1-i # 倒序
# 格式化输出1/2位数，y坐标轴
if temp >= 10:
print(temp, end=" ")
else:
print(temp, end=" ")
# 输出具体坐标的值，一行
for j in range(p):
print(x_y[j][temp], end=" ")
print("") #换行
# 输出 x 坐标轴
print(" ", end="")
for i in range(p):
if i >=10:
print(i, end=" ")
else:
print(i, end=" ")
print('\n')
def get_ng(G_x, G_y, key, a, p):
"""
计算nG
"""
temp_x = G_x
temp_y = G_y
while key != 1:
temp_x,temp_y = get_np(temp_x,temp_y, G_x, G_y, a, p)
key -= 1
return temp_x,temp_y
def ecc_main():
while True:
a = int(input("请输入椭圆曲线参数a(a>0)的值："))
b = int(input("请输入椭圆曲线参数b(b>0)的值："))
p = int(input("请输入椭圆曲线参数p(p为素数)的值：")) #用作模运算
# 条件满足判断
if (4*(a**3)+27*(b**2))%p == 0:
print("您输入的参数有误，请重新输入！！！\n")
else:
break
# 输出椭圆曲线散点图
get_graph(a, b, p)
# 选点作为G点
print("user1：在如上坐标系中选一个值为G的坐标")
G_x = int(input("user1：请输入选取的x坐标值："))
G_y = int(input("user1：请输入选取的y坐标值："))
# 获取椭圆曲线的阶
n = get_rank(G_x, G_y, a, b, p)
# user1生成私钥，小key
key = int(input("user1：请输入私钥小key（<{}）：".format(n)))
# user1生成公钥，大KEY
KEY_x,kEY_y = get_ng(G_x, G_y, key, a, p)
# user2阶段
# user2拿到user1的公钥KEY，Ep(a,b)阶n，加密需要加密的明文数据
# 加密准备
k = int(input("user2：请输入一个整数k（<{}）用于求kG和kQ：".format(n)))
k_G_x,k_G_y = get_ng(G_x, G_y, k, a, p) # kG
k_Q_x,k_Q_y = get_ng(KEY_x, kEY_y, k, a, p) # kQ
# 加密
plain_text = input("user2：请输入需要加密的字符串:")
plain_text = plain_text.strip()
#plain_text = int(input("user1：请输入需要加密的密文："))
c = []
print("密文为：",end="")
for char in plain_text:
intchar = ord(char)
cipher_text = intchar*k_Q_x
c.append([k_G_x, k_G_y, cipher_text])
print("({},{}),{}".format(k_G_x, k_G_y, cipher_text),end="-")
# user1阶段
# 拿到user2加密的数据进行解密
# 知道 k_G_x,k_G_y，key情况下，求解k_Q_x,k_Q_y是容易的，然后plain_text = cipher_text/k_Q_x
print("\nuser1解密得到明文：",end="")
for charArr in c:
decrypto_text_x,decrypto_text_y = get_ng(charArr[0], charArr[1], key, a, p)
print(chr(charArr[2]//decrypto_text_x),end="")
if __name__ == "__main__":
print("*************ECC椭圆曲线加密*************")
ecc_main()

复制代码

用户名		自动登录	找回密码
密码			立即注册

信息计算2019级1班19号谭斌斌

本帖子中包含更多资源