[發明專利]使用歐拉函數及中國剩余定理來拆分數據的方法

在審

• 申請號: 202011182903.8
• 申請日: 2020-10-29
• 公開（公告）號: CN112434107A
• 公開（公告）日: 2021-03-02
• 發明（設計）人: 龐皓天;李朋林;周俊;曹珍富;魏立斐;沈華杰;任成東
• 申請（專利權）人: 上海同態信息科技有限責任公司
• 主分類號: G06F16/27
• 分類號: G06F16/27;G06F21/62
• 代理公司: 北京科家知識產權代理事務所(普通合伙) 11427
• 代理人: 宮建華

1.使用歐拉函數及中國剩余定理來拆分數據的方法，包括數據發送方與數據接收方，其特征在于，包括以下步驟：

步驟1、系統初始化生成單項陷門置換(f，f^-1)，記單項陷門置換的公私鑰為(pk_f，sk_f)，其中發送方擁有pk_f，接收方擁有sk_f；

步驟2、數據發送方選擇安全參數λ，選擇大素數p，q，其中|q|＝|p|＝λ，計算N＝pq并公開N，將要拆分的數據表示為m，其中m＜N；

步驟3、數據發送發放進行數據計算：

m_p≡m mod p，m_q≡m mod q

公式中通過mod的求余運算，求出除m的余數，而后將獲得的兩個結果通過中國剩余定理構成同余方程；

使用歐式除法得到p和q的逆元：

1≡q^-1q mod p，1≡p^-1p mod q；

計算C₁＝f(p||r)，其中r為隨機數，得到密文C₁；

計算等到密文C₂；

數據發送方將C＝(C₁，C₂)發送給接收方；

步驟4、數據接收方獲得C之后，通過單項陷門求逆得到p||r＝f^-1(C₁)，去掉后面幾位r得到p，并通過計算q＝p^-1N得到q。；

步驟5、數據接收方進行計算：

c_q＝C₂mod q＝m_qmod q，

c_p＝C₂mod p＝m_pmod p，

通過m_q，m_p可使用中國剩余定理來恢復出m，其算法如下：

m＝m_p*q*q^-1+m_q*p*p^-1mod N。