分类目录归档:算法

Openssl源码方式添加国密SM2算法【轉】

【原文摘自】

http://blog.csdn.net/mrpre/article/details/51700884

【原文內容】

1:源码方式,只需要添加2部分,第一部分是 国密sm2的oid,第二部分是group。

如果不添加,则 EVP_PKEY 无法解析,ec_asn1_pkparameters2group 函数 因为找不到 oid对应的group导致解析私钥失败,或者解析x509的公钥为空。

注:如下修改 不会 让你支持生成SM2国密证书或者支持诸如ECC_SM4_SM3等国密加密套件。

该修改只是让你能够让openssl正常解密 sm2 证书。

1:添加sm2的oid

cd crypto/objects/

编辑  objects.txt ,添加: 1 2 156 10197 1 301: SM2: SM2

随便加在哪里即可,我添加在文件最后。

然后在当前目录下执行:
perl objects.pl objects.txt obj_mac.num obj_mac.h
perl obj_dat.pl obj_mac.h  obj_dat.h

2:添加 group

ec_curve.c 中添加 2 个定义:

static const struct { EC_CURVE_DATA h; unsigned char data[0+32*6]; }
_EC_X9_62_sm2 = {
{ NID_X9_62_prime_field,0,32,1 },
{  /* seed */
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,/* p */
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,    /* a */
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFc,
0x28,0xE9,0xFA,0x9E,0x9D,0x9F,0x5E,0x34,0x4D,0x5A,/* b */
0x9E,0x4B,0xCF,0x65,0x09,0xA7,0xF3,0x97,0x89,0xF5,
0x15,0xAB,0x8F,0x92,0xDD,0xBC,0xBD,0x41,0x4D,0x94,
0x0E,0x93,
0x32,0xC4,0xAE,0x2C,0x1F,0x19,0x81,0x19,0x5F,0x99,    /* x */
0x04,0x46,0x6A,0x39,0xC9,0x94,0x8F,0xE3,0x0B,0xBF,
0xF2,0x66,0x0B,0xE1,0x71,0x5A,0x45,0x89,0x33,0x4C,
0x74,0xC7,
0xBC,0x37,0x36,0xA2,0xF4,0xF6,0x77,0x9C,0x59,0xBD,    /* y */
0xCE,0xE3,0x6B,0x69,0x21,0x53,0xD0,0xA9,0x87,0x7C,
0xC6,0x2A,0x47,0x40,0x02,0xDF,0x32,0xE5,0x21,0x39,
0xF0,0xA0,
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, /* order */
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x72,0x03,0xDF,0x6B,
0x21,0xC6,0x05,0x2B,0x53,0xBB,0xF4,0x09,0x39,0xD5,
0x41,0x23}
};

curve_list 中添加:

{ NID_SM2, &_EC_X9_62_sm2.h, 0, “sm2 curve over a 256 bit prime field” },

然后重新make一下。

上述添加完成之后,OpenSSL即支持 SM2国密算法,能够正常解析 SM2国密证书。

 

【附】

需要將./crypto/objects/obj_mac.h移動到./include/openssl/obj_mac.h下,才能進行編譯

经典排序算法总结与实现「轉」

原文鏈接:http://xiaok.me/2015/08/27/%E7%BB%8F%E5%85%B8%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E4%B8%8E%E5%AE%9E%E7%8E%B0/

 

暑假快过完了也就大四了,马上就到了校招季了,作为一个才接触Android半年多的渣渣真的很慌张。最近打算复习一些算法和数据结构的知识,提升一下基础。这一篇是对经典排序算法的总结,共七个,可以说是手到擒来,提笔就要会的了。为了使代码易读,就用最简单的C语言实现了。

后面的排序默认从小到大排列

冒泡排序(Bubble sort)

原理

冒泡排序是一种简单的排序算法。它重复访问要排序的数列,每一次比较两个元素,如果前一个大于后一个元素,则交换数据。那么在一次全部访问过程中,最大的元素就’浮’动到数列的最后。然后重复进行方法,知道再没有数据交换,也就是数列已经排序完成。

步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

实现

void BubbleSort(int arr[], int n) {
    int i, j;
    i = n;
    bool flag = true;
    while (flag) {
        flag = false;
        for (j = 1; j < i; j++) {
            if (arr[j-1] > arr[j]) {
                swap(arr[j-1], arr[j]);
                flag = true;
            }
        }
        i--;
    }
}

在上面的代码中加入了一个flag来标记是否有数据交换,如果在排序过程中没发生数据交换,则表示已经排列好了,后面就不需要在遍历了。

冒泡排序算是最简单的排序算法了,但毕竟是一种效率低下的排序算法,再数据量不大的情况下可以使用。

插入排序(Insertion sort)

原理

插入排序是一种直观的排序算法。它通过构建有序数列,对未排序的数据,在已排序的数列中从后往前扫描,找到相应的位置插入。在排序的实现上,从后向前的扫描过程中,需要反复把已排序的元素逐步向后移动,为要插入的元素留空间。

步骤

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

实现

void InsertSort(int arr[], int n) {
    int i, j;
    for (i = 1;  i < n; i++) {
        if (arr[i] < arr[i-1]) {
            int temp = arr[i];
            for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }
}

插入排序不适合对于数据了比较大的排序应用。但是,如果排序数据了很小,比如一千左右,那插入排序是一个不错的选择。

选择排序(Selection sort)

原理

选择排序与插入排序很像,插入排序是将一个数插入已经排好的序列,而选择排序是在未排序的序列中找到最小(大)元素,放在排序序列的起始位置。然后,再从剩下的未排序的序列中再次寻找最小(大)元素,放在已排序序列的末尾,反复重复,知道所有元素排序完成。

步骤

  1. 初始时,数组全为无序区为a[0..n-1]。令i=0
  2. 在无序区a[i…n-1]中选取一个最小的元素,将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。
  3. i++并重复第二步直到i==n-1。排序完成。

实现

void SelectSort(int arr[], int n){
    int i, j, minIndex;
    for (i = 0; i < n; i++) {
        minIndex = i;
        for (j = i+1; j < n; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            Swap(arr[i],arr[minIndex]);
        }
    }
}

选择排序中,如果某个元素位于正确的最终位置,则不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移动到最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

希尔排序(Shell sort)

原理

希尔排序,也称作递减增量排序算法,是插入排序的一种更高效版本。它以一定的增量将序列分为若干个组,然后每一组进行插入排序,然后减少增量反复分组进行插入排序。直到增量为1时,就为普通的插入排序,但是此时序列已经基本排列完成,只需要进行少量的移动即可完成。

步骤

将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序(通过增加索引的步长,例如是用i += step_size而不是i++)

例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序(此时就是简单的插入排序了)。

实现

void ShellSort(int arr[], int n) {
    int i, j, gep;
    for (gep = n/2; gep > 0; gep /= 2) {
        for (i = gep; i < n; i++) {
            int temp = arr[i];
            for (j = i - gep; j >= 0 && arr[j] > temp; j-=gep) {
                arr[j+gep] = arr[j];
            }
            arr[j+gep] = temp;
        }
    }
}

希尔排序步长的选择十分灵活,只要最终步场为1的任何步长序列都可以工作。以上的代码从n/2开始,每一次减半,最终步长为1,算法变为插入排序,就保证了数据一定会被排序。

归并排序(Merge sort)

原理

归并排序是创建在归并操作上的一种有效的排序算法,基本思想是分治法。它时将两个已经排序的序列合并成一个序列的操作。

步骤

归并操作

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

归并排序

  1. 将序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素
  2. 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
  3. 重复步骤2,直到所有元素排序完毕

实现

//归并操作
void _merge_array(int arr[], int first, int mid, int last, int temp[]) {
    int i = first, j = mid + 1;
    int m = mid, n = last;
    int k = 0;
    while (i <= m && j <= n) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= m) {
        temp[k++] = arr[i++];
    }
    
    while (j <= n) {
        temp[k++] = arr[j++];
    }
    
    for (i = 0; i < k; i++) {
        arr[first + i] = temp[i];
    }
}

//归并排序
void _merge_sorte(int arr[], int first, int last, int temp[]) {
    if (first < last) {
        int mid = (first + last) / 2;
        _merge_sorte(arr, first, mid, temp);
        _merge_sorte(arr, mid+1, last, temp);
        _merge_array(arr, first, mid, last, temp);
    }
}

void MergeSort(int arr[], int n) {
    int *p = (int *)malloc(sizeof(int) * n);
    if (p != nullptr) {
        _merge_sorte(arr, 0, n-1, p);
    }
    free(p);
}

归并排序是分治法的典型应用,当一个数组的左右两边都有序然后归并整个数组就有序了,利用递归逐层分治,然后合并上来就排好序了。

快速排序(Quick sort)

快速排序算是我最喜欢的一个排序了,记得第一次接触的时候惊讶排序还可以这么排…题外话了

原理

快速排序也适用分治法,已一个数作为基准,左边全为笔它小的数,右边全为比它大的数。然后左右递归重复即可。

步骤

  1. 从数列中挑出一个元素,称为”基准”(pivot)
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

实现

下面列两种实现一种MoreWindows大神已挖坑填数总结的,一种是算法导论上的实现。

MoreWindows:

void QuickSort(int arr[], int l, int r) { 
    if (l < r) {
        int i = l, j = r;
        int k = arr[i];
        
        while (i < j) {
            while (i<j && arr[j] > k) {
                j--;
            }
            if (i<j) {
                arr[i++] = arr[j];
            }
            
            while (i<j && arr[i] <= k) {
                i++;
            }
            if (i<j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = k;
        
        QuickSort(arr, l, i-1);
        QuickSort(arr, i+1, r);
    }
}

算法导论 :

int quick_sort(int arr[], int left, int right) {
    int index = left;
    int k = arr[index];
    
    Swap(arr[index],arr[right]);
    for (int i = left; i < right; i++) {
        if (arr[i] < k) {
            Swap(arr[index++], arr[i]);
        }
    }
    Swap(arr[index], arr[right]);
    return index;
}

void QuickSort(int arr[], int left, int right) {
    if (left < right) {
        int index = quick_sort(arr, left, right);
        QuickSort1(arr, left, index-1);
        QuickSort1(arr, index+1, right);
    }
}

快速排序递归下去的最低情形,是数列的大小0或1,也就是永远排好了序。在每一次递归中至少有一个数会摆到它最后的位置。

堆排序(Heap sort)

堆排序对于我而言算是比较难搞懂的排序了

原理

堆排序是利用堆这种数据结构所设计的一种排序算法。最大(小)堆的根节点 为整个序列的最大(小)数。堆每取出一个根节点,堆被破坏,然后堆就会调整使之符合最大(小)堆。那么依次取出堆的根节点,依次放入新的数列中,直到堆元素为0位置,那么新的数列已经排好序了。

步骤

堆节点的访问:

通常堆是通过一维数组来实现的。在起始数组为0的情形中:

  • 父节点i的左子节点在位置(2*i+1);
  • 父节点i的右子节点在位置(2*i+2);
  • 子节点i的父节点在位置floor((i-1)/2);

堆的操作:

在堆的数据结构中,堆中的最大值总是位于根节点。堆中定义以下几种操作:

  • 最大堆调整(Max_Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  • 创建最大堆(Build_Max_Heap):将堆所有数据重新排序
  • 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

原地堆排序:

  1. 创建一个堆H[0..n-1]
  2. 把堆首(最大值)和堆尾互换
  3. 把堆的尺寸缩小1,并调用MaxPrcdown(),目的是把新的数组顶端数据调整到相应位置
  4. 重复步骤2,直到堆的尺寸为1

实现

void MaxPrcdown(int arr[], int i, int n) {
    int temp = arr[i];
    int chlid = 2 * i + 1;
    while (chlid < n) {
        if (chlid + 1 < n && arr[chlid] < arr[chlid+1]) {
            chlid++;
        }
        
        if (arr[chlid] <= temp) {
            break;
        }
        
        arr[i] = arr[chlid];
        i = chlid;
        chlid = 2 * i + 1;
    }
    arr[i] = temp;
}

void HeapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i>=0; i--) {
        MaxPrcdown(arr, i, n);
    }
    for (int i = n - 1; i >= 1; i--) {
        Swap(arr[0], arr[i]);
        MaxPrcdown(arr, 0, i);
    }
}

总结

 

排序算法 最差时间复杂度 平均时间复杂度 空间复杂度 稳定性
冒泡排序 O(n^2) O(n^2) O(1) 稳定
插入排序 O(n^2) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(1) 稳定
归并排序 O(nlogn) O(nlogn) O(n) 不一定
希尔排序 O O O(1) 不稳定
快速排序 O(n^2) O(nlogn) O(logn)~O(n) 不稳定
堆排序 O(n*log2n) O(n*log2n) O(1) 不稳定

 

参考