RSA加密算法的有效实现及在云计算中的应用

谢会娟　韩昌豪　吴明珠

摘要：随着互联网的发展，云计算模式能够提供便捷的、可用的和按需要网络资源，云计算的核心是如何存储和管理用户的数据，除了配置存储设备的之外，还要考虑到存储在云中的数据的安全性。RSA加密算法是基于一个比较简单的数论—两个大素数相乘十分容易实现，但要对它的乘积进行因式分解却十分困难，RSA加密算法是将乘积公开作为加密密钥的非对称加密方法，在云计算中应用RSA算法对存储在云中的数据进行加密，能够保证了数据的安全性。

关键词：RSA算法；云安全；素数

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）14-3263-03

Abstract：With the development of the Internet， cloud computing can provide convenient and available network resources， the core of cloud computing is how to store and manage user data， cloud computing does not provide storage devices， but also takes into account the security of the data stored in the cloud. RSA encryption algorithm is based on a relatively simple theory of math - multiplying two large prime numbers is very easy to achieve， but it's the factorization is very difficult， RSA encryption algorithm considers a product as a public encryption key and is an asymmetric encryption method. To ensure the security of the data， RSA encryption algorithm is applied for the data storage in the cloud.

Key words： RSA algorithm； cloud security； prime

RSA公钥密码算法是1978年以它的三个发明者Rivest，Shamir， Adleman的名字首字母命名，RSA方案是唯一被广泛接受并实现的通用公开密钥密码算法[1]。在“云”时代，每时每刻都有加密信息在传输、存储、处理和交换，一旦密码被攻击者破解可能会造成不可估量的严重后果，如何有效地保障信息的安全成为当今云时代的比较有研究价值的课题。

1 RSA算法的描述

现在明文空间K=密文空间C=Zm（表示mod m所组成的整数空间，即其取值范围为0～n-1）

第一步 生成密钥

1）选择2个足够大的互异素数p和q，p和q的值要保密；

2） 计算m的值，m=p×q，m的值是公开的；

3） 计算n的值，n=（p-1）×（q-1），n是保密的；

4）选择一个公开的随机整数e，要求0

5） 计算t=e-1mod n，t的值要保密，其中{t，m}为私钥。

第二步 加密

若明文K≥m，需要对大的报文进行分组，保证每个分组都要满足K

第三步 解密

使用私钥{t，m}进行解密，其中K=Ct mod n。

2 有效实现RSA算法的三个关键算法

2.1 扩展的欧几里德算法

在RSA算法中，{t，m}为私钥，其中t 的值为e-1mod n即t是e的逆元，计算逆元要使用扩展的欧几里德算法，算法如下所示：

2.2快速指数算法

在RSA算法的运算中，加密C=Ke mod m和解密M =Ct mod n的过程中，都用到了快速指数运算。由于数字比较大，本算法是只适用于模拟使用，因而采用了long型存储，在实际应用中，会因为公钥或密钥过长而产生溢出，使程序运行出错，若改用Java语言中的BingInteger类来存储数据可以解决溢出问题。

一般情况下是使用降价方法实现指数运算，但是会占用较大的内存空间，为了有效地进行指数运算，在每次执行乘法前用模的方法来降阶，即快速指数算法。快速指数算法描述为m的二进制表示为bkbk-1...b0，其中bi={0，1}（i=0，1，...，k），则m=[i=0kbi2i=bi=12i]。因此，有[ammodn=abi=12imodn=bi=1a（2i）modn=bi=1[a（2i）modn]modn][1]。

算法描述如下 ：

2.3自动生成两个大素数

RSA算法是首个比较流行的公开密钥算法，不但用于加密，也广泛用于数字签名。三十多年以来RSA算法经受住了各种攻击的考验，既不能证明也不能否定RSA的安全性，具有一定的可信性，被认为是目前最优秀的公钥方案之一，生成两个大素数p和q的算法是RSA的核心算法，为了增强算法的可操作性和应用性，下生算法实现了自动生成两个大素数，算法如下所示：

云计算环境具有存储数据和处理数据等特点，使得云计算平台中的安全需求也多种多样，这对密码学的研究及应用提出了挑战。对云计算实行应用与服务相结合的密码机制，并采用高效率的密钥管理方法，可以在一定程度上解决云端数据安全的问题[2]。用户把数据存储在云端，云服务商将负责数据的存储、管理及数据安全等工作，如图1所示。RSA加密算法可用于加密云中的数据，因为 RSA的安全性依赖于大数分解的难度，也就是把一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积的难度，这是公认的数学难题。在云计算中使用RSA算法要先生成一对RSA 密钥，一个是由用户保存的保密密钥，另一个是可对外公开的公开密钥，甚至可在云服务器中注册，为了能够提高云存储数据的保密强度，RSA密钥要长于500位，推荐使用1024位，为了减少计算量，在传送信息时，通常采用传统加密方法和公开密钥加密方法相结合的方式进行加密。

参考文献：

[1] 胡向东，魏琴芳，胡蓉.应用密码学[M].北京：电子工业出版社，2011：134-138.

[2] 张晨.RSA密码算法在云计算中的应用[J].信息技术与标准化，2013：55-56.

摘要：随着互联网的发展，云计算模式能够提供便捷的、可用的和按需要网络资源，云计算的核心是如何存储和管理用户的数据，除了配置存储设备的之外，还要考虑到存储在云中的数据的安全性。RSA加密算法是基于一个比较简单的数论—两个大素数相乘十分容易实现，但要对它的乘积进行因式分解却十分困难，RSA加密算法是将乘积公开作为加密密钥的非对称加密方法，在云计算中应用RSA算法对存储在云中的数据进行加密，能够保证了数据的安全性。

关键词：RSA算法；云安全；素数

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）14-3263-03

Abstract：With the development of the Internet， cloud computing can provide convenient and available network resources， the core of cloud computing is how to store and manage user data， cloud computing does not provide storage devices， but also takes into account the security of the data stored in the cloud. RSA encryption algorithm is based on a relatively simple theory of math - multiplying two large prime numbers is very easy to achieve， but it's the factorization is very difficult， RSA encryption algorithm considers a product as a public encryption key and is an asymmetric encryption method. To ensure the security of the data， RSA encryption algorithm is applied for the data storage in the cloud.

Key words： RSA algorithm； cloud security； prime

RSA公钥密码算法是1978年以它的三个发明者Rivest，Shamir， Adleman的名字首字母命名，RSA方案是唯一被广泛接受并实现的通用公开密钥密码算法[1]。在“云”时代，每时每刻都有加密信息在传输、存储、处理和交换，一旦密码被攻击者破解可能会造成不可估量的严重后果，如何有效地保障信息的安全成为当今云时代的比较有研究价值的课题。

1 RSA算法的描述

现在明文空间K=密文空间C=Zm（表示mod m所组成的整数空间，即其取值范围为0～n-1）

第一步 生成密钥

1）选择2个足够大的互异素数p和q，p和q的值要保密；

2） 计算m的值，m=p×q，m的值是公开的；

3） 计算n的值，n=（p-1）×（q-1），n是保密的；

4）选择一个公开的随机整数e，要求0

5） 计算t=e-1mod n，t的值要保密，其中{t，m}为私钥。

第二步 加密

若明文K≥m，需要对大的报文进行分组，保证每个分组都要满足K

第三步 解密

使用私钥{t，m}进行解密，其中K=Ct mod n。

2 有效实现RSA算法的三个关键算法

2.1 扩展的欧几里德算法

在RSA算法中，{t，m}为私钥，其中t 的值为e-1mod n即t是e的逆元，计算逆元要使用扩展的欧几里德算法，算法如下所示：

2.2快速指数算法

在RSA算法的运算中，加密C=Ke mod m和解密M =Ct mod n的过程中，都用到了快速指数运算。由于数字比较大，本算法是只适用于模拟使用，因而采用了long型存储，在实际应用中，会因为公钥或密钥过长而产生溢出，使程序运行出错，若改用Java语言中的BingInteger类来存储数据可以解决溢出问题。

一般情况下是使用降价方法实现指数运算，但是会占用较大的内存空间，为了有效地进行指数运算，在每次执行乘法前用模的方法来降阶，即快速指数算法。快速指数算法描述为m的二进制表示为bkbk-1...b0，其中bi={0，1}（i=0，1，...，k），则m=[i=0kbi2i=bi=12i]。因此，有[ammodn=abi=12imodn=bi=1a（2i）modn=bi=1[a（2i）modn]modn][1]。

算法描述如下 ：

2.3自动生成两个大素数

RSA算法是首个比较流行的公开密钥算法，不但用于加密，也广泛用于数字签名。三十多年以来RSA算法经受住了各种攻击的考验，既不能证明也不能否定RSA的安全性，具有一定的可信性，被认为是目前最优秀的公钥方案之一，生成两个大素数p和q的算法是RSA的核心算法，为了增强算法的可操作性和应用性，下生算法实现了自动生成两个大素数，算法如下所示：

云计算环境具有存储数据和处理数据等特点，使得云计算平台中的安全需求也多种多样，这对密码学的研究及应用提出了挑战。对云计算实行应用与服务相结合的密码机制，并采用高效率的密钥管理方法，可以在一定程度上解决云端数据安全的问题[2]。用户把数据存储在云端，云服务商将负责数据的存储、管理及数据安全等工作，如图1所示。RSA加密算法可用于加密云中的数据，因为 RSA的安全性依赖于大数分解的难度，也就是把一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积的难度，这是公认的数学难题。在云计算中使用RSA算法要先生成一对RSA 密钥，一个是由用户保存的保密密钥，另一个是可对外公开的公开密钥，甚至可在云服务器中注册，为了能够提高云存储数据的保密强度，RSA密钥要长于500位，推荐使用1024位，为了减少计算量，在传送信息时，通常采用传统加密方法和公开密钥加密方法相结合的方式进行加密。

参考文献：

[1] 胡向东，魏琴芳，胡蓉.应用密码学[M].北京：电子工业出版社，2011：134-138.

[2] 张晨.RSA密码算法在云计算中的应用[J].信息技术与标准化，2013：55-56.

摘要：随着互联网的发展，云计算模式能够提供便捷的、可用的和按需要网络资源，云计算的核心是如何存储和管理用户的数据，除了配置存储设备的之外，还要考虑到存储在云中的数据的安全性。RSA加密算法是基于一个比较简单的数论—两个大素数相乘十分容易实现，但要对它的乘积进行因式分解却十分困难，RSA加密算法是将乘积公开作为加密密钥的非对称加密方法，在云计算中应用RSA算法对存储在云中的数据进行加密，能够保证了数据的安全性。

关键词：RSA算法；云安全；素数

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）14-3263-03

Abstract：With the development of the Internet， cloud computing can provide convenient and available network resources， the core of cloud computing is how to store and manage user data， cloud computing does not provide storage devices， but also takes into account the security of the data stored in the cloud. RSA encryption algorithm is based on a relatively simple theory of math - multiplying two large prime numbers is very easy to achieve， but it's the factorization is very difficult， RSA encryption algorithm considers a product as a public encryption key and is an asymmetric encryption method. To ensure the security of the data， RSA encryption algorithm is applied for the data storage in the cloud.

Key words： RSA algorithm； cloud security； prime

RSA公钥密码算法是1978年以它的三个发明者Rivest，Shamir， Adleman的名字首字母命名，RSA方案是唯一被广泛接受并实现的通用公开密钥密码算法[1]。在“云”时代，每时每刻都有加密信息在传输、存储、处理和交换，一旦密码被攻击者破解可能会造成不可估量的严重后果，如何有效地保障信息的安全成为当今云时代的比较有研究价值的课题。

1 RSA算法的描述

现在明文空间K=密文空间C=Zm（表示mod m所组成的整数空间，即其取值范围为0～n-1）

第一步 生成密钥

1）选择2个足够大的互异素数p和q，p和q的值要保密；

2） 计算m的值，m=p×q，m的值是公开的；

3） 计算n的值，n=（p-1）×（q-1），n是保密的；

4）选择一个公开的随机整数e，要求0

5） 计算t=e-1mod n，t的值要保密，其中{t，m}为私钥。

第二步 加密

若明文K≥m，需要对大的报文进行分组，保证每个分组都要满足K

第三步 解密

使用私钥{t，m}进行解密，其中K=Ct mod n。

2 有效实现RSA算法的三个关键算法

2.1 扩展的欧几里德算法

在RSA算法中，{t，m}为私钥，其中t 的值为e-1mod n即t是e的逆元，计算逆元要使用扩展的欧几里德算法，算法如下所示：

2.2快速指数算法

在RSA算法的运算中，加密C=Ke mod m和解密M =Ct mod n的过程中，都用到了快速指数运算。由于数字比较大，本算法是只适用于模拟使用，因而采用了long型存储，在实际应用中，会因为公钥或密钥过长而产生溢出，使程序运行出错，若改用Java语言中的BingInteger类来存储数据可以解决溢出问题。

一般情况下是使用降价方法实现指数运算，但是会占用较大的内存空间，为了有效地进行指数运算，在每次执行乘法前用模的方法来降阶，即快速指数算法。快速指数算法描述为m的二进制表示为bkbk-1...b0，其中bi={0，1}（i=0，1，...，k），则m=[i=0kbi2i=bi=12i]。因此，有[ammodn=abi=12imodn=bi=1a（2i）modn=bi=1[a（2i）modn]modn][1]。

算法描述如下 ：

2.3自动生成两个大素数

RSA算法是首个比较流行的公开密钥算法，不但用于加密，也广泛用于数字签名。三十多年以来RSA算法经受住了各种攻击的考验，既不能证明也不能否定RSA的安全性，具有一定的可信性，被认为是目前最优秀的公钥方案之一，生成两个大素数p和q的算法是RSA的核心算法，为了增强算法的可操作性和应用性，下生算法实现了自动生成两个大素数，算法如下所示：

云计算环境具有存储数据和处理数据等特点，使得云计算平台中的安全需求也多种多样，这对密码学的研究及应用提出了挑战。对云计算实行应用与服务相结合的密码机制，并采用高效率的密钥管理方法，可以在一定程度上解决云端数据安全的问题[2]。用户把数据存储在云端，云服务商将负责数据的存储、管理及数据安全等工作，如图1所示。RSA加密算法可用于加密云中的数据，因为 RSA的安全性依赖于大数分解的难度，也就是把一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积的难度，这是公认的数学难题。在云计算中使用RSA算法要先生成一对RSA 密钥，一个是由用户保存的保密密钥，另一个是可对外公开的公开密钥，甚至可在云服务器中注册，为了能够提高云存储数据的保密强度，RSA密钥要长于500位，推荐使用1024位，为了减少计算量，在传送信息时，通常采用传统加密方法和公开密钥加密方法相结合的方式进行加密。

参考文献：

[1] 胡向东，魏琴芳，胡蓉.应用密码学[M].北京：电子工业出版社，2011：134-138.

[2] 张晨.RSA密码算法在云计算中的应用[J].信息技术与标准化，2013：55-56.