美文网首页Android开发经验谈Android开发数据结构和算法分析
算法09-加密与解密

算法09-加密与解密

作者: 最爱的火 | 来源:发表于2018-05-29 08:11 被阅读18次

    算法09-加密与解密

    一、介绍

    加密，是以某种特殊的算法改变原有的信息数据，使得未授权的用户即使获得了已加密的信息，但因不知解密的方法，仍然无法了解信息的内容。

    解密，是使用特定的密钥来还原加密过的信息。

    加密之所以安全，绝非因不知道加密解密算法，而是加密的密钥是绝对的隐藏，流行的RSA和AES加密算法都是完全公开的，一方取得已加密的数据，就算知道加密算法也好，若没有加密的密钥，也不能打开被加密保护的信息。

    在Android中，加密常用于信息传输和信息存储。

    常见的加密算法：SHA1、DES、Base64、RSA。

    二、SHA1算法

    1、基本思想

    数字签名

    数字签名的原理是将要传送的明文通过一种函数运算（Hash）转换成报文摘要（不同的明文对应不同的报文摘要），报文摘要加密后与明文一起传送给接受方，接受方将接受的明文产生新的报文摘要与发送方的发来报文摘要解密比较，比较结果一致表示明文未被改动，如果不一致表示明文已被篡改。

    SHA1

    安全哈希算法（Secure Hash Algorithm）主要适用于数字签名标准 （Digital Signature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA），是一种不需要解密的算法。对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。

    SHA1有如下特性：

    1. 不可以从消息摘要中复原信息；
    2. 两个不同的消息不会产生同样的消息摘要(有10 ^ 48分之一的机率出现相同的消息摘要,一般可以忽略)。
    3. SHA1算法中，消息相当于密钥，一个初始int数组RS相当于原消息。标准的SHA1算法使用统一的RS，自己实现SHA1算法时，可以修改RS的初始值。

    SHA1同类算法：SHA224 、SHA256、 SHA384 、SHA512 、MD5 、HmacMD5、HmacSHA1 、HmacSHA224 、HmacSHA256 、HmacSHA384 、HmacSHA512 、PBKDF2。

    2、代码实现

    SHA1的实现分为以下步骤：

    1、转位字符串

    将消息摘要S转换成位字符串，这里我们为了方便计算，将S转为byte数组SD，将SD对应的位字符串叫做SB；

    2、补位

    消息必须进行补位，即使消息之前已经满足条件，补位后SB的长度%512 = 448。补位规则是，在SB的后面一位补1，其余位补0。最少需要补1位，最多补512（即2的64次方）位。

    由于这里使用byte[]操作，所以添加的第一个byte为0x80，后面添加0x00。

    3、添加长度

    用一个64位的位字符串表示原始SB的长度，把这个位字符串添加到补位后的SB后面。这样得到的SB的长度就是512的倍数。

    这里先把原始SD的长度转为long类型的原始SB的长度addLen，然后把addLen转为byte数组，添加到SD后面。

    4、初始化数据

    用5个32的二进制数来保存加密的结果，这里我们使用长度为5的int数组RS来表示。我们还需要给RS设定初始值，统一使用下面的初始值：

    int[] RS = {0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0};

    声明一个长度为80的int数组M来保存加密的中间结果，对M的前16位进行初始化：将SB分成n块，每块为512位的位字符串。将每个512位的位字符串平分成16份，放到M的前16位中，然后对M进行加密。加密操作见步骤5。

    5、加密

    加密分为以下几步：

    1. 补齐M：从M的第i(16<=i<=79)位开始，通过函数S(data,k)=(data << k) | (data >>> (32 - k))来补齐，这里k传入1，data传入M[i - 3] ^ M[i - 8] ^ M[i - 14] ^ M[i - 16];
    2. 声明函数与常量。声明4个函数：f1(x, y, z)= (x & y) | (~x & z); f2(x, y, z) =x ^ y ^ z;f3(x, y,z)= (x & y) | (x & z) | (y & z);f4(x, y, z=x ^ y ^ z。声明4个常量：K1 = 0x5A827999 ；K2 = 0x6ED9EBA1 ；K3= 0x8F1BBCDC ；K4= 0xCA62C1D6。
    3. 修改RS。
      1. 声明：先声明一个临时的int数组TRS,最初TRS=RS，声明一个临时的int值temp。
      2. 遍历M:从M的第i(0<=i<=79)位开始，TRS[4] = TRS[3];TRS[3] = TRS[2];TRS[2] = s(TRS[1], 30);TRS[1] = TRS[0];TRS[0] = temp。
      3. 计算temp：当0<=i<=19时，temp = S(TRS[0], 5) + f1(TRS[1], TRS[2], TRS[3]) + TRS[4] + M[i] + K1;当20<=i<=39时，temp = S(TRS[0], 5) + f2(TRS[1], TRS[2], TRS[3]) + TRS[4] + M[i] + K2;当40<=i<=59时，temp = S(TRS[0], 5) + f3(TRS[1], TRS[2], TRS[3]) + TRS[4] + M[i] + K4;当60<=i<=79时，temp = S(TRS[0], 5) + f4(TRS[1], TRS[2], TRS[3]) + TRS[4] + M[i] + K4;
      4. 修改RS：从TRS的i位开始，RS[i]+=TRS[i]。然后清空M。

    6、转换结果

    当SB的n块都加密完了，就得到了最终的结果RS。将RS转成16进制的字符串输出即可。

    关键代码：

    /**
 * @param s 需要加密的数据
 * @param R 初始结果集,决定加密的最终结果
 */
public static String SHA(String s, int[] R) {
    //1、转位字符串
    byte[] SD = convertBitString(s);
    //2、补位
    SD = coverPosition(SD);
    //3、添加长度
    SD = addLength(SD, s.getBytes().length);
    //4、初始化数据并进行加密
    int[] RS = initData(R, SD);
    //6、转换结果
    String result = convertHexString(RS);
    return result;
}

/**
 * 1、转位字符串
 * @param s 原消息
 * @return 转换的byte数组
 */
private static byte[] convertBitString(String s) {
    if (Tool.isEmpty(s)) {
        return null;
    }
    byte[] data = s.getBytes();
    return data;
}

/**
 * 2、补位
 * @param data 原消息S的byte数组SD
 * @return 补位后的SD
 */
private static byte[] coverPosition(byte[] data) {
    if (data == null || data.length == 0) {
        return null;
    }
    // 补0x00的个数
    int fill = 0;
    // 原数组的长度
    int length = data.length;
    //相当于SB的长度%512
    int m = length % 64;
    //如果m小于56，就补1个0x80和55-m个0x00
    if (m < 56) {
        fill = 55 - m;
        //如果56<=m<64，就补1个0x80和(64 - m)+55个0x00。
    } else {
        fill = 55 + 64 - m;
    }

    //补位结果
    byte[] result = new byte[data.length + 1 + fill];
    //拷贝data
    System.arraycopy(data, 0, result, 0, length);
    // 补1个0x80
    result[length] = (byte) 0x80;
    //补fill个0x00,由于默认值就是0，所以不用操作
    return result;
}

/**
 * 3、添加长度
 * @param data  补位后的SD
 * @param lengh 原SD的大小
 * @return 增加长度后的SD
 */
private static byte[] addLength(byte[] data, int lengh) {
    if (data == null || data.length == 0) {
        return null;
    }
    //结果:增加8个byte，相当于增加64位的位字符串
    byte[] result = new byte[data.length + 8];
    //拷贝data
    System.arraycopy(data, 0, result, 0, data.length);
    //增加的长度
    long addLen = lengh * 8;
    //将增加的长度转byte数组
    byte[] lengthByte = ToolMath.longToBytes(addLen);
    System.arraycopy(lengthByte, 0, result, data.length, lengthByte.length);
    return result;
}

/**
 * 4、初始化数据
 * @param R  初始结果集
 * @param SD 增加长度后的SD
 * @return 加密结果
 */
private static int[] initData(int[] R, byte[] SD) {
    // 加密结果
    int[] RS = new int[5];
    //RS的初始值是R
    System.arraycopy(R, 0, RS, 0, R.length);
    // 加密的中间数据
    int[] M = new int[80];

    // 计算有几个512位的二进制数据
    int count = SD.length / 64;
    // 循环计算每一块的内容
    for (int i = 0; i < count; i++) {
        //将每个512位的位字符串平分成16份，放到M的前16位中
        for (int j = 0; j < 16; j++) {
            M[j] = byteArrayToInt(SD, i * 64 + j * 4);
        }
        //对RS加密
        encode(M, RS);
    }
    return RS;
}

/**
 * 5、加密
 * @param m 加密的中间数据
 * @param h 加密结果
 */
public static void encode(int[] m, int[] h) {
    //1.补齐M
    for (int i = 16; i <= 79; i++) {// 补齐m
        m[i] = s(m[i - 3] ^ m[i - 8] ^ m[i - 14] ^ m[i - 16], 1);
    }
    //2.声明函数与常量
    int K1 = 0x5A827999, K2 = 0x6ED9EBA1, K3 = 0x8F1BBCDC, K4 = 0xCA62C1D6;

    //3. 修改RS。
    //3.1 声明临时数组TRS，并初始化
    int[] TRS = new int[5];
    System.arraycopy(h, 0, TRS, 0, h.length);
    //3.2 遍历M并计算temp
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j <= 19; j++) {
            int index = i * 20 + j;
            int temp = 0;
            if (i == 0) {
                temp = s(TRS[0], 5) + f1(TRS[1], TRS[2], TRS[3]) + TRS[4] + m[index] + K1;
            } else if (i == 1) {
                temp = s(TRS[0], 5) + f2(TRS[1], TRS[2], TRS[3]) + TRS[4] + m[index] + K2;
            } else if (i == 2) {
                temp = s(TRS[0], 5) + f3(TRS[1], TRS[2], TRS[3]) + TRS[4] + m[index] + K3;
            } else if (i == 3) {
                temp = s(TRS[0], 5) + f4(TRS[1], TRS[2], TRS[3]) + TRS[4] + m[index] + K4;
            }
            TRS[4] = TRS[3];
            TRS[3] = TRS[2];
            TRS[2] = s(TRS[1], 30);
            TRS[1] = TRS[0];
            TRS[0] = temp;
        }
    }

    //3.4修改RS，并清空M
    for (int i = 0; i < TRS.length; i++) {
        h[i] += TRS[i];
    }
    for (int i = 0; i < m.length; i++) {
        m[i] = 0;
    }
}

/**
 * 6、转换结果
 * @param RS 加密结果
 * @return 转换后16进制字符串结果
 */
private static String convertHexString(int[] RS) {
    if (Tool.isEmpty(RS)) {
        return null;
    }
    StringBuffer sb = new StringBuffer();
    for (int in : RS) {
        byte[] bytes = ToolMath.intToBytes(in);
        sb.append(ToolMath.bytesToHexString(bytes));
    }
    return sb.toString();
}

    三、RSA算法

    1、基本思想

    非对称加密算法

    非对称加密算法是一种密钥的保密方法。

    非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。 非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。

    RSA加密算法

    RSA加密算法是一种非对称加密算法,在公开密钥加密和电子商业中RSA被广泛使用。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的三十多年里，经历了各种攻击的考验，逐渐为人们接受，截止2017年被普遍认为是最优秀的公钥方案之一。

    缺点与不足：加密和解密花费时间长、速度慢，只适合对少量数据进行加密。

    RSA的原理：

    1.公钥生成:公钥由n和e组成。n=P*Q,P和Q都是素数，例如：n=53*59=3127。e是一个不能整除n且介于1与PHI(n)=(P-1)*(Q-1)之间的整数，例如:e=3。

    2.私钥生成：私钥d=(2*PHI(n)+1)/e，例如：d=(2*(53-1)*(59-1)+1)/3=2011。

    3.使用公钥加密数据：把明文的每一位转换成数字 如HI=89，密文c=明文^e%n， 例如:c=89^3%3127=1394。

    4.使用私钥解密数据：明文=c^d%n， 例如:明文=1394^2011% 3127=89。

    2、代码实现

    /**
 * 生成密钥对
 * 这里使用KeyPairGenerator来生产密钥对，KeyPairGenerator初始化需要传入密钥位数和一个安全的随机数
 *
 * @param publicKeyFile  公钥存放的文件
 * @param privateKeyFile 私钥存放的文件
 * @throws Exception
 */
public static void createKey(String publicKeyFile, String privateKeyFile) throws Exception {
    // 安全的随机数
    SecureRandom sr = new SecureRandom();
    // 生成密钥工具类
    KeyPairGenerator kpg = KeyPairGenerator.getInstance(ALGORITHM);
    // KEYSIZE必须是64的倍数，在512--65536之间 默认1024
    kpg.initialize(KEYSIZE, sr);
    // 生成密钥对
    KeyPair kp = kpg.generateKeyPair();
    // 获取公钥
    Key publicKey = kp.getPublic();
    // 获取私钥
    Key privateKey = kp.getPrivate();
    // 保存公钥
    ToolFile.writeObject(publicKeyFile, publicKey);
    // 保存私钥
    ToolFile.writeObject(privateKeyFile, privateKey);
}

/**
 * 加密
 * 使用Cipher来加密，先声明Cliper的类型为RSA加密，然后Cipher初始化需要传入模式为加密模式和之前生成的公钥
 *
 * @param msg           明文
 * @param publicKeyFile 公钥存放的文件
 * @return
 * @throws Exception
 */
public static String encode(String msg, String publicKeyFile) throws Exception {
    if (Tool.isEmpty(msg) || Tool.isEmpty(publicKeyFile)) {
        return null;
    }
    // 获取公钥
    Key key = (Key) ToolFile.readObject(publicKeyFile);
    //设置为RSA加密类型
    Cipher cip = Cipher.getInstance(ALGORITHM);
    // 设置为加密模式，并传入公钥
    cip.init(Cipher.ENCRYPT_MODE, key);
    //加密结果
    byte[] result = cip.doFinal(msg.getBytes());
    //再使用Base64加密一次
    String s = Base64.encodeToString(result, Base64.DEFAULT);
    return s;
}

/**
 * 解密
 * 使用Cipher来解密，传入模式为解密模式和之前生成的私钥
 *
 * @param msg            密文
 * @param privateKeyFile 私钥存放的文件
 * @return
 * @throws Exception
 */
public static String decode(String msg, String privateKeyFile) throws Exception {
    if (Tool.isEmpty(msg) || Tool.isEmpty(privateKeyFile)) {
        return null;
    }
    // 获取私钥
    Key key = (Key) ToolFile.readObject(privateKeyFile);
    //设置为RSA加密类型
    Cipher cip = Cipher.getInstance(ALGORITHM);
    //设置为解密模式，并传入私钥
    cip.init(Cipher.DECRYPT_MODE, key);
    //先得到Base64的解密结果
    byte[] result = Base64.decode(msg.getBytes(), Base64.DEFAULT);
    //再得到RSA的解密结果
    result = cip.doFinal(result);
    String s = new String(result);
    return s;
}

    四、DES算法

    DES全称为Data Encryption Standard，即数据加密标准，是一种使用密钥加密的块算法，是对称密钥算法。DES算法的入口参数有三个：Key、Data、Mode。其中Key为7个字节共56位，是DES算法的工作密钥；Data为8个字节64位，是要被加密或被解密的数据，使用时会将原数据分成不同的块来操作；Mode为DES的工作方式,有两种:加密或解密。

    DES设计中使用了分组密码设计的两个原则：混淆（confusion）和扩散(diffusion)，其目的是抗击敌手对密码系统的统计分析。混淆是使密文的统计特性与密钥的取值之间的关系尽可能复杂化，以使密钥和明文以及密文之间的依赖性对密码分析者来说是无法利用的。扩散的作用就是将每一位明文的影响尽可能迅速地作用到较多的输出密文位中，以便在大量的密文中消除明文的统计结构，并且使每一位密钥的影响尽可能迅速地扩展到较多的密文位中，以防对密钥进行逐段破译。

    DES的密钥较短，加密处理简单，加解密速度快，适用于加密大量数据的场合。

    DES同类算法：AES、RC4、Rabbit、TripleDes。

    五、Base64算法

    Base64是网络上最常见的用于传输8Bit字节码的编码方式之一，Base64就是一种基于64个可打印字符来表示二进制数据的方法。

    Base64编码方法要求把每三个8Bit的字节转换为四个6Bit的字节，其中，转换之后的这四个字节中每6个有效bit为是有效数据，空余的那两个 bit用0补上成为一个字节。因此Base64所造成数据冗余不是很严重，Base64是当今比较流行的编码方法，因为它编起来速度快而且简单。

    Base64的作用：

    1. 统一编码。由于某些系统中只能使用ASCII字符。Base64就是用来将非ASCII字符的数据转换成ASCII字符的一种方法。
    2. 降低可读性。采用Base64编码具有不可读性，需要解码后才能阅读。

    最后

    代码地址：https://gitee.com/yanhuo2008/Common/tree/master/Tool/src/main/java/gsw/tool/arithmetic/encode

    数据结构与算法专题：https://www.jianshu.com/nb/25128590

    喜欢请点赞，谢谢！

    相关文章

      网友评论

        本文标题：算法09-加密与解密

        本文链接：https://www.haomeiwen.com/subject/nhkojftx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        Android开发经验谈

        Android开发

        数据结构和算法分析

        关于我们|服务条款|联系我们|算法09-加密与解密|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！