[PDF] rsa formula
[PDF] rsa signature
[PDF] rsa video maker
[PDF] rselenium findelement
[PDF] rselenium mac
[PDF] rselenium navigate
[PDF] rselenium rsdriver
[PDF] rselenium sendkeystoelement
[PDF] rselenium tutorial
[PDF] rspca first aid guide
[PDF] rspca pet first aid kit
[PDF] rss channel list youtube
[PDF] rssb
[PDF] rstudio desctools
[PDF] rstudio tutorial pdf
The RSA Cryptosystem
Dan Boneh
Stanford University
Page 2
The RSA cryptosystem
ØFirst published:
•Scientific American, Aug. 1977. (after some censorship entanglements) ØCurrently the "work horse" of Internet security: •Most Public Key Infrastructure (PKI) products. •SSL/TLS: Certificates and key-exchange. •Secure e-mail: PGP, Outlook, ...
Page 3
The RSA trapdoor permutation
ØParameters:N=pq. N »1024 bits. p,q »512 bits. e -encryption exponent. gcd(e, j(N) ) = 1 . ØPermutation:RSA(M) = Me(mod N) where MÎZNØTrapdoor:d-decryption exponent.
Where e×d= 1 (mod j(N) )
ØInversion:RSA(M)d= M(mod N)
Ø"Assumption":
no efficient alg. can invert RSA without trapdoor.
Page 4
Textbook RSA is insecure
ØTextbook RSA encryption:
•public key: (N,e)Encrypt: C = Me(mod N) •private key: dDecrypt: Cd= M(mod N) (M ÎZN)
ØCompletely insecure cryptosystem:
•Does not satisfy basic definitions of security. •Many attacks exist. ØThe RSA trapdoor permutation is not a cryptosystem !
Page 5
A simple attack on textbook RSA
ØSession-key K is 64 bits. View K Î{0,...,264}
Eavesdropper sees: C = Ke(mod N).
ØSuppose K = K1×K2where K1, K2< 234. (prob. »20%)
Then: C/K1e= K2e(mod N)
ØBuild table: C/1e, C/2e, C/3e, ..., C/234e. time: 234 For K2= 0,..., 234test if K2eis in table. time: 234×34
ØAttack time: »240 << 264Web
BrowserWeb
ServerCLIENT HELLO
SERVER HELLO (e,N)d
C=RSA(K)Random
session- key K
Page 6
Common RSA encryption
ØNever use textbook RSA.
ØRSA in practice:
ØMain question:
•How should the preprocessing be done? •Can we argue about security of resulting system?msgPreprocessingciphertextRSA
Page 7
PKCS1 V1.5
ØPKCS1 mode 2:(encryption)
ØResulting value is RSA encrypted.
ØWidely deployed in web servers and browsers.
ØNo security analysis !!02random padFFmsg
1024 bits
16 bits
Page 8
Attack on PKCS1
ØBleichenbacher98. Chosen-ciphertext attack.
ØPKCS1 used in SSL:
Þattacker can test if 16 MSBsof plaintext = '02'.
ØAttack: to decrypt a given ciphertext C do:
•Pick random r ÎZN. Compute C'= re×C = (rM)e. •Send C'to web server and use response.AttackerWeb
ServerdIs this
PKCS1?ciphertext
C=C
Yes: continue
No: error02
Page 9
Chosen ciphertext security (CCS)
ØNo efficient attacker can win the following game: (with non-negligible advantage)AttackerChallengerM
0, M1b'Î{0,1}
Attacker wins if b=b'C=E(M
b) bÎR{0,1}
ChallengeDecryption
oracle ¹C
Page 10
Chosen-ciphertext secure RSA
ØAre there CCS cryptosystems based on RSA?
•RSA-PKCS1 is not CCS !
ØAnswer: Yes!Dolev-Dwork-Naor(DDN). 1991.
•Problem: inefficient. ØOpen problem: efficient CCS system based on RSA.
ØWhat to do? Cheat!
•Build RSA system that is CCS in imaginary world. •"Assume" our-world = imaginary-world.
Page 11
PKCS1 V2.0 -OAEP
ØNew preprocessing function: OAEP (BR94).
ØThm: "trap-door permutation F ÞF-OAEP is CCS when H,G are "random oracles".
ØIn practice: use SHA-1 or MD5 for H and G.H+
G+
Plaintext to encryptwith RSArand.M0100..0
Check pad
on decryption.
Reject CT if invalid.
Î{0,1}n-1
Page 12
An incorrect proof
ØShoup2000: The OAEP thmcannot be correct !!
ØCounter ex: f(x)-xormalleable trapdoor permutation f(x), DÞf(xÅD) Define: h(x,y) = [ x, f(y) ](also trapdoor perm)
ØAttack on h-OAEP:AttackerChallengerM
0, M1C = h(OAEP(Mb)) = [x,f(y)]Rand D= r||01000
y'= yÅG(x)ÅG(xÅD)
C'= [ xÅD, f(y') ]Decrypt C' (¹C)M
b ÅDM b
Page 13
Consequences
ØOAEP is standardized due to an incorrect thm.
ØFortunately: Fujisaki-Okamoto-Pointcheval-Stern •RSA-OAEP is Chosen CiphertextSecure !! -Proof uses special properties of RSA.
ÞNo immediate need to change standards.
•Security proof less efficientthan original "proof". uMain proof idea [FOPS]: •For Shoup'sattack: given challenge C = RSA(x ||y) attacker must "know" x •RSA(x ||y) Þx then RSA is not one-way.
Page 14
OAEP Replacements
ØOAEP+: (Shoup'01)
"trap-door permutation F
F-OAEP+ is CCS when
H,G,W are "random oracles".
ØSAEP+: (B'01)
RSA trap-door perm Þ
RSA-SAEP+ is CCS when
H,W are "random oracle".R
H+
G+MW(M,R)
R
H+MW(M,R)
Page 15
Subtleties in implementing OAEP
OAEP-decrypt(C) {
error = 0; if (RSA-1(C) > 2n-1) { error =1; gotoexit; } if (pad(OAEP-1(RSA-1(C))) != "01000" ) { error = 1; gotoexit; }} ØProblem:timing information leaks type of error.
ÞAttacker can decrypt any ciphertextC.
ØLesson: Don't implement RSA-OAEPyourself ...
Part II:
Is RSA a One-Way Permutation?
Page 17
Is RSA a one-way permutation?
ØTo invert the RSA one-way function (without d) attacker must compute:
M from C = Me(mod N).
ØHow hard is computing e'throots modulo N??
ØBest known algorithm:
•Step 1: factor N. (hard) •Step 2: Find e'throots modulo p and q. (easy)
Page 18
Shortcuts?
ØMust one factor N in order to compute e'throots? Exists shortcut for breaking RSA without factoring?
ØTo prove no shortcut exists show a reduction:
•Efficient algorithm for e'throots mod N
Þefficient algorithm for factoring N.
•Oldest problem in public key cryptography.
ØEvidence no reduction exists:(BV'98)
•"Algebraic" reduction Þfactoring is easy. •Unlike Diffie-Hellman(Maurer'94).
Page 19
Improving RSA'sperformance
ØTo speed up RSA decryption use
small private key d.Cd= M (mod N) •Wiener87:if d < N0.25then RSA is insecure. •BD'98:if d < N0.292then RSA is insecure (open: d < N 0.5 ) •Insecure:priv. key d can be found from (N,e). •Small d should neverbe used.
Page 20
Wiener's attack
ØRecall:e×d = 1 (mod j(N) )
Þ$kÎZ : e×d = k×j(N) + 1
j(N) = N-p-q+1 Þ|N-j(N)| £p+q £3ÖN d £N0.25/3 Þ
Continued fraction expansion of e/N gives k/d.
e×d = 1 (mod k) Þgcd(d,k)=1e j(N) k d -£ 1 dj(N) e N k d -£ 1 2d2
Page 21
RSA With Low public exponent
ØTo speed up RSA encryption (and sig. verify)
use a small e.C = Me(mod N)
ØMinimal value: e=3( gcd(e, j(N) ) = 1)
ØRecommended value: e=65537=216+1
Encryption: 17 mod. multiplies.
ØSeveral weak attacks. Non known on RSA-OAEP.
ØAsymmetry of RSA: fast enc. / slow dec.
•ElGamal: approx. same time for both.
Page 22
Implementation attacks
ØAttack the implementation of RSA.
ØTiming attack: (Kocher97)
The time it takes to compute Cd(mod N)
can expose d.
ØPower attack: (Kocher99)
The power consumption of a smartcard while
it is computing Cd(mod N) can expose d.
ØFaults attack: (BDL 97)
A computer error during Cd(mod N)
can expose d.
OpenSSL defense: check output. 5%slowdown.
Page 23
Key lengths
ØSecurity of public key system should be
comparable to security of block cipher. NIST:
Cipher key-sizeModulus size
£64 bits512 bits.
80 bits1024 bits
128 bits3072 bits.
256 bits (AES)15360bits
ØHigh security Þvery large moduli.
Not necessary with Elliptic Curve Cryptography.
quotesdbs_dbs14.pdfusesText_20
[PDF] The RSA Cryptosystem - Stanford University