RSA-256bit Digital Circuit Lab TA: Po-Chen Wu.

Slides:



Advertisements
Similar presentations
期末考试作文讲解 % 的同学赞成住校 30% 的学生反对住校 1. 有利于培养我们良好的学 习和生活习惯; 1. 学生住校不利于了解外 界信息; 2 可与老师及同学充分交流有 利于共同进步。 2. 和家人交流少。 在寄宿制高中,大部分学生住校,但仍有一部分学生选 择走读。你校就就此开展了一次问卷调查,主题为.
Advertisements

中考读写. News Chapter 4 a collection of collect v. 收集 这家博物馆拥有精美的绘画收藏品。 一群人;一批物品 收集者、收藏家 collector The museum has a fine collection of paintings.
高考数学专题之概率 高考数学冲刺 主讲人 : 北京大学光华管理学院 何洋. 北京师范大学京师大厦 9810 室 电话 : 传真 : 写在前面的话 概率是高中数学新教材中新增的内容, 在 实际生活中应用非常广泛, 并且由于概率 论是统计学的基础,
第四講:分數數概念與加減運算 分數代表什麼 ? ½ 是什麼意思呢 ? 分數的意義 分數是用來表示不滿一個單位量的數值,其中 涉及「等分」的概念與等分的「測量活動」。 目前課程多以將指定一個單位,切分成另外一 個小單位後,對小單位重新以大單位加以命名。 並以具體物介紹分數,情境上分為連續量與離 散量。
去 上 海 看 世 博 Qù Shànghǎi kàn shìbó
企业培训师培训(上) 王 囤 副教授.
說 劍 《莊子‧雜篇》─ 第 一 組 賴泊錞 謝孟儒 張維真 羅苡芸
第6章: 完整性与安全性 域约束 参照完整性 断言 触发器 安全性 授权 SQL中的授权.
電子商務安全防護 線上交易安全機制.
質數的應用 – RSA加密演算法 國立中央大學 資工系 江振瑞.
Chapter 1: 概論 1.1 密碼學術語簡介及假設
-CHINESE TIME (中文时间): Free Response idea: 你周末做了什么?
數學解題王 ~從閱讀策略談起 分享者:吳祥銘老師.
英语语法之 复合句 讲课者:苏建玉.
06資訊安全-加解密.
欢迎再次走进 思想政治的课堂.
第四章 时间序列的分析 本章教学目的:①了解从数量方面研究社会经济现象发展变化过程和发展趋势是统计分析的一种重要方法;②掌握时间数列编制的基本要求;③理解和掌握水平速度两方面指标的计算及运用④理解和掌握长期趋势分析和预测的方法。 本章教学重点:现象发展的水平指标和速度指标。 本章教学难点:现象变动的趋势分析。
5B 教材分析.
第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案. 第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案.
國語科補救教學 龍華國小 許如菁.
公開鑰匙加密演算法 密碼學大革命 public key所想要解決的問題 public key密碼系統特性
Euler’s method of construction of the Exponential function
CH1 Number Systems and Conversion
第十三章 收入和利润.
RSA Cryptosystem Theorem 1.3: For n = p * q p,q 均是質數
網路與多媒體實驗 第一組報告 B 鄧鎮海 B 葉穎達
社會學(一) 空中大學花蓮中心 鍾燕菁
二、現代的加解密法:RSA 非對稱式密碼系統的一種。
Chapter 4 歸納(Induction)與遞迴(Recursion)
学练优英语教学课件 八年级(上) it! for Go
第三章 公钥基础设施PKI 本章学习重点掌握内容: 密码学基本术语 密码体制分类 私钥密码体制的主要特点 公钥密码体制的主要特点
CH19資訊安全 認識資訊安全與其重要性 了解傳統與公開金鑰密碼系統, 以及基本的安全性觀念 了解訊息鑑別與雜湊函數 了解數位簽章法
附錄 密碼學基本觀.
Short Version : 6. Work, Energy & Power 短版: 6. 功,能和功率
基礎密碼學 非對稱式金鑰加密法 樹德科技大學 資訊工程系 林峻立 助理教授.
主讲人: 吕敏 { } Spring 2016,USTC 算法基础 主讲人: 吕敏 { } Spring 2016,USTC.
李开祥 郭雪丽 马高峰 杨洋 孙凤英 陈静 Copyright © 2007 西安交通大学电子商务系
I've been thinking for a long time about what we do in our life...
Chapter 3 Nationality Objectives:
4-5 数论基础.
A Big Basketball Fan 执教:百草园小学 邹建芬.
Chp.4 The Discount Factor
高中英语语法专项训练 补中训练 九 名词性从句 重庆二外左明正 九 名词性从句
公開金鑰密碼系統 (Public-Key Cryptosystems)
计算机问题求解 – 论题3-2 - 贪心算法 2018年09月18日.
Mechanics Exercise Class Ⅰ
Guide to a successful PowerPoint design – simple is best
每周三交作业,作业成绩占总成绩的15%; 平时不定期的进行小测验,占总成绩的 15%;
Chp.4 The Discount Factor
公钥密码学与RSA.
應用加密技術 A 譚惠心 指導教授:梁明章教授.
所以我們需要     密碼學…. 每個人都有秘密….. 安俐的體重.
Chp.4 The Discount Factor
高考应试作文写作训练 5. 正反观点对比.
9/27 今天的学习目标 (Today’s Learning Objectives)
生成树.
WIRELESS LAN B 邱培哲 B 張宏安.
An Efficient MSB Prediction-based Method for High-capacity Reversible Data Hiding in Encrypted Images 基于有效MSB预测的加密图像大容量可逆数据隐藏方法。 本文目的: 做到既有较高的藏量(1bpp),
演算法分析 (Analyzing Algorithms)
Chapter 7 Relations (關係)
Hashing Michael Tsai 2017/4/25.
國立東華大學課程設計與潛能開發學系張德勝
_14RSA加密的基本原理 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
计算机问题求解 – 论题 串匹配 2017年5月3日.
Class imbalance in Classification
張仁俊 (Jen-Chun Chang) 國立台北大學 資訊工程學系 通訊工程研究所 電機工程研究所
Climbing a Rock Wall 攀岩 选自《多维阅读第10级》.
陳情表之外     with 三仁 三樂 歐陽宜璋製於 /10/23.
Hybrid fractal zerotree wavelet image coding
Presentation transcript:

RSA-256bit Digital Circuit Lab TA: Po-Chen Wu

Outline Introduction to Cryptography RSA Algorithm Montgomery Algorithm for RSA-256 bit

Introduction to Cryptography

Communication Is Insecure Alice Bob Paparazzi

Secure Approach: Cryptosystems Alice Bob Paparazzi

Cryptosystems Encryption Scheme Decryption Scheme Alice Bob Encryption Key Decryption Key

Encryption vs. Decryption Only Bob knows the decryption key. Encryption Key Only Alice and Bob know the encryption key: PRIVATE cryptosystem Everyone knows the encryption key: PUBLIC cryptosystem RSA is a public cryptosystem.

RSA Algorithm

RSA Cryptosystem If Bob wants to use RSA, he needs to select a key pair, and announce the encryption key. If Alice wants to communicate with Bob, she needs to use the encryption key announced by Bob. If Bob wants to receive messages from the others, he needs to use the decryption key he selected.

How to Select a key pair Key pair selection scheme: Bob (randomly) selects 2 prime numbers p and q. For security reason, p = 2p' + 1 and q = 2q' + 1, where p' and q' are also prime numbers. Bob evaluates n = pq and Ф(n) = (p −1)(q − 1) Bob chooses e such that gcd(e, Ф(n)) = 1 Bob finds the integer d (0 < d < Ф(n)) such that ed − kФ(n) = 1 Finally, Bob announces the number pair (n, e) and keeps (d, p, q, Ф(n)) in secret. Euler's totient or phi function, Ф(n) counts the integers between 1 and n that are coprime to n. Ф(p) = p − 1, Ф(q) = q − 1 Ф(pq) = (p − 1)(q − 1)

How to Encrypt Encryption Scheme: Whenever Alice wants to tell Bob m which is less than n, she evaluate c = me mod n, where n and e are the numbers Bob announced. Then Alice sends c to Bob.

How to Decrypt Decryption Scheme: Why the decryption scheme work? Whenever Bob receives an encrypted message c, he evaluate m' = cd mod n Fact: m' = m Why the decryption scheme work? Euler's theorem: if gcd(a, n)=1, aФ(n) mod n = 1 cd mod n = (me mod n) d mod n =(me)d mod n = med mod n = mkФ(n)+1 mod n =(mk)Ф(n)m mod n = m Hard to calculate! 這裡的a (a.k.a. mk) 也有可能使得gcd(a, n)!=1 但機率實在是低得離譜,大概是(2^128+2^128-1)/2^255 也就是1/2^127 左右 而駭客只要把d找出來就可以得到m 要找d就要解出ed − kФ(n) = 1 要解上述式子就得知道Ф(n)長怎樣 而要知道Ф(n)必須將n拆成p&q 所以只要能將n拆成p&q,就能破解RSA了 所以p&q要夠大夠複雜,n才不好拆,d才難求

Montgomery Algorithm for RSA-256 bit

Inverse (1/4) For real number, x and y are the inverse of each other if We write y = x−1, and vice versa. When we say a divided by b, or a / b, we mean that a multiplied by b−1. In the “world” of “modulo N,” we want to define the inverse (and then the division operator / ) such that the exponential laws hold. xy = 1

Inverse (2/4) For a positive integer x (< N), We define the inverse of in the “world” of “modulo N” is the positive integer y (< N) such that We write y = x−1, and vice versa. We define the “division” in the “world” of “modulo N” as xy mod N = 1 在mod的世界裡,正整數x的inverse,是一個正整數叫做y 這個y能夠使得xy mod N = 1 我們可以寫做y = x−1(所以x−1是一個正整數!) 而所有的division我們都要看成是 x / y mod N = xy−1 mod N 而y−1是一個正整數 (這樣就不會有分數的情況出現了) x / y mod N = xy−1 mod N

Inverse (3/4) Theorem: If b = an, then b / a mod N = n. Example: a = 2, N = 35, then a−1 = 18 b = 12 = 2 * 6, b / a mod N = ba−1 mod N = 12 * 18 mod 35 = 216 mod 35 = 6

Inverse (4/4) Another example: a = 2, N = 35, then a−1 = 18 b = 13 b / a mod N = ba−1 mod N = 13 * 18 mod 35 = 234 mod 35 = 24 or b / a mod N = (b + N) / a mod N = (13 + 35 ) / 2 mod 35 = 24 所以計算b / a mod N 有兩種方法 ba−1 mod N (b直接成a−1) (b + kN) / a mod N , k ∈ integer (把b + kN弄成是a的倍數直接除,不用真的做mod)

MSB-Based Modular Multiplication We want to evaluate V ≡ AB (mod N), where A = 2n-1an-1+2n-2an-2+…+2a1+a0 We can find that V ≡ {2[…(2(2an-1B + an-2B) + an-3B) + …+ a1B] + a0B} The Algorithm for MSB-Based Modular Multiplication Vn ← 0 for i = n − 1, …,1,0 Vi ← (2Vi+1 + ai.B) mod N 2Vi+1 + aiB < 3N

Square and Multiplication Algorithms for Modular Exponentiation Evaluate S = Me mod N where exponent e=(1ek-2…e1e0) No need to be k bit MSB-ME( Me mod N) S ← M for i = k − 2, …,1,0 S ← (S.S) mod N if (ei = 1) S ← (S.M) mod N LSB-ME(Me mod N) S ← 1, T ← M for i = 0,1,…, k − 1 if (ei = 1) S ← (S.T) mod N T ← (T.T) mod N LSB是比較直覺的想法,T是temp的意思,每次T是M^1, M^2, M^4, 然後看S要不要乘(如果e_i = 1就乘T) MSB比較潮,因為一開始一定是1,所以可以省一次,S一開始就是M,然後會變成M^2, M^4,…,中間如果遇到e_i = 1就乘個M (所以之後可能變成M^3這樣) (A·B) mod N is still hard to implement

Montgomery Algorithm Idea: Trying to compare Vi with N costs a lot. Idea: How about LSB first to evaluate the multiplication? mod不是那麼好計算的

Montgomery Algorithm: Phase 1 Evaluate Vn=(A·B·2-n) mod N A.B.2-n = B.2-n.(2n-1an-1+2n-2an-2+…+2a1+a0 ) = B.(2-1an-1+2-2an-2+…+2-(n-1)a1+2-na0 ) = 2-1(an-1B +2-1(an-2B+…+2-1(a1B+2-1a0B)…)) V0 ← 0 for i = 0,1,…, n−1 Vi+1 ← Vi + aiB 2 mod N Vi+ aiB 2 mod N = Vi+ aiB+qiN 2 , qi = LSB of (Vi+ aiB) 在mod的世界裡,/2不是真的除2 因為 Vi +aiB 2 一定會小於N,所以 1. 若是Vi+ aiB為2的倍數,那 Vi+aiB 2 mod N 就是 Vi+aiB 2 2. 但若Vi+ aiB不是2的倍數,怎麼辦? 其實就是直接把Vi+ aiB再加N後一起除2就好 因為有沒有加N,最後做mod時結果應該是要一樣的,但是由於Vi+aiB+N會是2的倍數,所以好處理很多 可是 Vi+ aiB+qiN 2 可能會大於N,就不是真的 Vi+ aiB 2 mod N 的解,怎辦? 其實就是最後再檢查就好 (接下頁) LSB modular reduction Vi + aiB 2 mod N is easy!

Montgomery Algorithm: Phase 2 When to substitute? V0 ← 0 for i = 0,1,…, n−1 qi ← (Vi +aiB) mod 2 Vi+1 ← Vi + aiB +qiN 2 if (Vn ≥ N) V ← Vn − N A=(an-1an-2…a1a0)2 , A,B<N V0=0<2N, Vi+1 ≤ Vi + aiB + N 2 < 2N, i=0,1,…,n-1

Montgomery Algorithm: Modified Version (1/2) A.B.2-n = B.2-n.(2n-1an-1+2n-2an-2+…+2a1+a0 ) = B.(2-1an-1+2-2an-2+…+2-(n-1)a1+2-na0 ) = 2-2((2an-1+an-2)B +2-2((2an-3+an-4)B+… + 2-2((2a3+a2)B + 2-2(2a1+a0)B)…)) V0 ← 0 for i = 0,2,…, n−2 Vi+2 ← Vi + 2ai+1B + aiB 4 mod N 另外由於N是p*q = (2p’+1)*(2q’+1) 所以N mod 4 = (4p’ q’+2p’+2q’+1) mod 4 因為p’ mod 4 = 1or3, so 2p’ mod 4 =2 (2p’+2q’) mod 4 = 0 => (4p’ q’+2p’+2q’+1) mod 4 = 1 Vi + 2ai+1B + aiB 4 mod N = Vi + 2ai+1B + aiB + qiN 4 , qi = (ki = 0)? 0: (4−ki), ki = (Vi + 2ai+1B + aiB) mod 4

Montgomery Algorithm: Modified Version (2/2) for i = 0,2,…, n−2 ki = (Vi + 2ai+1B + aiB) mod 4 qi = (ki = 0)? 0: (4−ki); Vi+2 ← Vi + 2ai+1B + aiB + qiN 4 if (Vn ≥ N) V ← Vn − N 因為V_i<2N儲存 所以Vi + 2ai+1B + aiB < 5N -> 要用259bit去存 Vi + 2ai+1B + aiB + (4−ki)N < 8N -> 也是用259bit去存 A=(an-1an-2…a1a0)2 , A,B<N V0=0<2N, Vi+2 ≤ Vi + 2ai+1B+aiB+3N 4 < 2N, i=0,1,…,n-1

Modular Exponentiation Using Montgomery Algorithm (1/2) Observation on Vn = MA(A, B) = (A·B·2-n) mod N Define A' = 2nA mod N (A “packed”) Fact: If V = AB mod N, then V = MA(A', B) Fact: If V = AB mod N, then V' = MA(A', B') Idea: “Pack” the integers we want to evaluate, and use Montgomery Algorithm instead of direct modular multiplication.

Modular Exponentiation Using Montgomery Algorithm (2/2) Evaluate S = Me mod N Constant C = 22n mod N MSB-ME( Me mod N) M ' ← MA(C.M) (pre-processing) S ← M ' for i = k − 2, …,1,0 S ← MA(S.S) if (ei = 1) S ← MA(S.M ') S ← MA(S.1) (post-processing) LSB-ME( Me mod N) T ← MA(C.M) (pre-processing) S ← 1 for i = 0,1,…, k − 1 if (ei = 1) S ← MA(S.T) T ← MA(T.T) 把原本的(A·B) mod N的部份都變成MA(),這樣會好計算許多 另外pre-processing的部份,不用真的實作MA,只要作2nM mod N就可以 (M乘二,檢查是否要減N<-循環) MSB-ME( Me mod N) S ← M for i = k − 2, …,1,0 S ← (S.S) mod N if (ei = 1) S ← (S.M) mod N LSB-ME(Me mod N) S ← 1, T ← M for i = 0,1,…, k − 1 if (ei = 1) S ← (S.T) mod N T ← (T.T) mod N

The End. Any question?

Reference [1] P.L. Montgomery, “Modular multiplication without trial division,”Mathematics of Computation, vol.44, pp.519-521, April 1985.