ECC(Elliptic Curves Cryptography) 椭圆曲线加密原理

2018/09/07

ECC(Elliptic Curves Cryptography) 属于非对称加密算法的一个重要组成部分。
本文尽量简单地阐述椭圆曲线加密的原理,但需要读者有一些初级的数论与离散数学相关的知识,或者推荐简单地阅读《算法导论》第31章:数论算法。

椭圆曲线

首先需要明确的是,我们讨论的是什么样的曲线。
椭圆曲线有比较复杂的定义: https://en.wikipedia.org/wiki/Elliptic_curve .而我们讨论的椭圆曲线比这个简单,它是以下方程所描述的一条平滑曲线 :

$$y^2 = x^3 + ax + b, 4a^3 + 27b^2 \neq 0$$

它描述的并不是一个椭圆,之所以称它为”椭圆曲线方程”, 是因为它源自于求椭圆弧长的椭圆积分的反函数。椭圆曲线是无奇点的,即没有尖点,且不会自相交。当 $a,b$ 的值不同时,椭圆曲线会表现出不同的形态:

而当 $4a^3 + 27b^2 = 0$ 时, 它不是椭圆曲线:

从图中可以看到,椭圆曲线总是 沿 x 轴对称 的。这是因为 $y^2$ 的存在。特殊地,我们规定 无穷远点 也存在于椭圆曲线上。我们用 $0$ 或符号 $O$ 来表示无穷远点,则椭圆曲线在实数域上的定义如下:
$$\{ (x,y) \in \mathbb{R}^2 | y^2 = x^3 + ax + b, 4a^3 + 27b^2 \neq 0 \} \cup \{0\}$$

阅读全文…

国密之 sm4 分组密码算法

2018/08/23

SM4分组密码算法,原名SMS4,国家密码管理局于2012年3月21日发布,相关标准为“GM/T 0002-2012《SM4分组密码算法》(原SMS4分组密码算法)”。它是一种分组对称加密算法,分组长度和密钥长度均为 128bit ,加密算法与密码扩展算法均采用 32 轮非线性迭代结构, Sbox 为固定的 8bit 输入 8bit 输出的置换。 数据加/解密的算法结构相同,只是轮密钥的使用顺序相反,解密轮密钥是加密轮密钥的逆序。

SBox

在密码学中,Sbox(Substitution-box,替换盒)是对称密钥加密算法执行替换计算的基本结构。SBox接受一个特定位数的输入,通过查表将其转换为特定位数的输出。SM4 给定的 SBox 如下:

0 1 2 3 4 5 6 7 8 9 A B C D E F
0 D6 90 E9 FE CC E1 3D B7 16 B6 14 C2 28 FB 2C 05
1 2B 67 9A 76 2A BE 04 C3 AA 44 13 26 49 86 06 99
2 9C 42 50 F4 91 EF 98 7A 33 54 0B 43 ED CF AC 62
3 E4 B3 1C A9 C9 08 E8 95 80 DF 94 FA 75 8F 3F A6
4 47 07 A7 FC F3 73 17 BA 83 59 3C 19 E6 85 4F A8
5 68 6B 81 B2 71 64 DA 8B F8 EB 0F 4B 70 56 9D 35
6 1E 24 0E 5E 63 58 D1 A2 25 22 7C 3B 01 21 78 87
7 D4 00 46 57 9F D3 27 52 4C 36 02 E7 A0 C4 C8 9E
8 EA BF 8A D2 40 C7 38 B5 A3 F7 F2 CE F9 61 15 A1
9 E0 AE 5D A4 9B 34 1A 55 AD 93 32 30 F5 8C B1 E3
A 1D F6 E2 2E 82 66 CA 60 C0 29 23 AB 0D 53 4E 6F
B D5 DB 37 45 DE FD 8E 2F 03 FF 6A 72 6D 6C 5B 51
C 8D 1B AF 92 BB DD BC 7F 11 D9 5C 41 1F 10 5A D8
D 0A C1 31 88 A5 CD 7B BD 2D 74 D0 12 B8 E5 B4 B0
E 89 69 97 4A 0C 96 77 7E 65 B9 F1 09 C5 6E C6 84
F 18 F0 7D EC 3A DC 4D 20 79 EE 5F 3E D7 CB 39 48

例如,对于输入 EF, 通过查表输出为 第 E 行,第 F 列,84

阅读全文…

electron 调用 c++ 踩坑笔记

2018/06/27

当前的一个项目想使用 Electron 做个 Demo 来进行测试,在调用 C++ 时遇到了一些坑,踩坑的过程中发现网上踩这些坑的人还不少,踩完坑在这里顺手记录一下。

x86 OR x64

lib 的位数与 node.js 的位数必须一致,而和操作系统的位数无关,当然,32位的操作系统是无法运行64位的应用程序 的。

ps: 如何查文件是32位还是64位

  • 记得自己下载安装的是什么版本(废话)
  • Windows 下:可以使用 vs 自带的 SDK Tools, 执行命令:

阅读全文…

在 Qt 中使用 TreeView

2018/05/11

提示:本文中的 Demo 已 push 到 github,可忽略本文直接到 我的github 中查看代码。

Qt 提供了 QuickControl TreeView 。但是比较奇葩的是该控件不能直接使用,而需要用户自己扩展实现。
官方给出了一个示例如下:

它声明了一个 TreeView控件,该控件有 2 列,分别为 Name 和 Permissions,还有一个名为 fileSystemModel 的 model 。对用户来说,这里的 model 是一个关键性的对象,它需要用户使用 C++ 实现 ,并注册到 qml 中供 TreeView 使用。按官方的说法, model 是一个 为 tree view 提供数据的属性,它包含了 tree view 将要展示的数据
用户的 model 必须继承于 QAbstractItemModel
该类是一个抽象类,在运行中,treeview 从该类中获取用户数据,再在UI上展示。该类有如下纯虚函数,必须在子类中实现:

阅读全文…

Coding , 333

CMake 为项目添加自定义事件

2018/04/26

为满足需求:

项目编译前需要预处理一些自定义命令,如生成代码文件,拷贝成果文件等。

解决该问题有两种方案:

add_custom_command prebuild

vcxproj 可以自定义生成事件,如:

阅读全文…

Note 352

多线程编程中的一些原则

2018/03/19

关于 C++ 多线程编程一的些基本知识可以参考本博客的《C++11/14 新特性(多线程)》 ,《Unix线程基础》。本章不是多线程编程教程,而是个人经验的一些总结。这些经验有一些可能是不正确的,希望在今后的编程中实践、改进。

线程同步的四项基本原则:

  1. 最低限度地共享对象。对象尽量不要暴露给别的线程,如果需要暴露,优先考虑 immutable对象。否则尽量使用同步措施来充分地保护它
  2. 尽量使用高级地并发编程构件,如 任务队列、生产者消费者模式等
  3. 只用非递归的互斥器和条件变量,慎用读写锁,尽量少用信号量
  4. 除了使用 atomic 整数外,不要自己编写 lock-free 代码,也不要用”内核级”同步原语

互斥器 Mutex

mutex 是最常用的同步原语,它保护一个临界区,任何时候最多只能有一个线程能够访问 mutex 保护的域。使用 mutex 主要是为了保护共享数据。一般原则有:

  • 使用 RAII手法封装 mutex 的创建、销毁、加锁、解锁操作,充分保证锁的有效期等于其作用域,而不会因为中途返回或异常而忘记解锁。这类似于 Java 的synchronized 或 C# 的 using 语句。
  • 使用非递归的 mutex
  • 尽量不要人为地调用 lock()unlock()函数,将这些操作交给栈上的 guard 对象,利用其构造与析构函数。
  • 不要跨线程地加解锁,避免在不同的函数中分别加锁\解锁,避免在不同的语句分支中加锁\解锁
  • 每当构造 guard 对象时,需要考虑栈上已有的锁,防止因加锁顺序不同而导致死锁
  • 避免跨进程的 mutex, 进程间通讯尽量使用 TCP sockets

只使用非递归地 mutex

阅读全文…