Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

X-Ray Diffraction

Loading...

Published in: Physics
3,790 Views

X-Ray diffraction

Narendra K / Mumbai

8 years of teaching experience

Qualification:

Teaches: Chemistry, Mathematics, Physics, B.Sc Tuition, CTET, KVPY Exam

Contact this Tutor
  1. Elliptic Curve Cryptography Speaker : Debdeep Mukhopadhyay Dept of Computer Sc and Engg 11T Madras
  2. Outline of the Talk... Introduction to Elliptic Curves Elliptic Curve Cryptosystems (ECC) Implementation of ECC in Binary Fields
  3. Introduction to Elliptic Curves
  4. Lets start with a puzzle... What is the number of balls that may be piled as a square pyramid and also rearranged into a square array? Soln: Let x be the height of the pyramid... Thus, 12 +22 +32 -k...+x 6 We also want this to be a square: Hence, 2 6
  5. Graphical Representation Y axis X axis Curves of this nature are called ELLIPTIC CURVES
  6. Method of Diophantus Uses a set of known points to produce new points (0,0) and (1 , 1) are two trivial solutions Equation of line through these points is y=x. Intersecting with the curve and rearranging terms: 3 3 x 2 2 We know that 1 +0 + x = 3/2 x = 1/2 and y = lh Using symmetry of the curve we also have (1/2,-1/2) as another solution
  7. Diophantus' Method Consider the line through (1/2,-1/2) and (1 , 1) Y=3x-2 Intersecting with the curve we have: 51 3 x 2 Thus 1/2+1 + x = 51/2 or x = 24 and y=70 Thus if we have 4900 balls we may arrange them in either way
  8. Elliptic curves in Cryptography Elliptic Curve (EC) systems as applied to cryptography were first proposed in 1985 independently by Neal Koblitz and Victor Miller. , The discrete logarithm problem on elliptic curve groups is believed to be more difficult than the corresponding problem in (the multiplicative group of nonzero elements of) the underlying finite field.
  9. Discrete Logarithms in Finite Fields Pick secret, random X from F Alice mod p gy mod p Pick secret, random Y from F Bob Compute mod p Compute mod p Eve has to compute gXY from gx and W without knowing x and y... She faces the Discrete Logarithm Problem in finite fields
  10. Elliptic Curve on a finite set of Consider x x x x x 2 Integers (mod 5) 3 no solution (mod 5) 6 15 36 75 1,4 (mod 5) 0 (mod 5) 1,4 (mod 5) 0 (mod 5) Then points on the elliptic curve are and the point at infinity: Using the finite fields we can form an Elliptic Curve Group where we also have a DLP problem which is harder to solve...
  11. Definition of Elliptic curves elliptic curve over a field K is a nonsingular An cubic curve in two variables, f(x,y) with a rational point (which may be a point at infinity). The field Kis usually taken to be the complex numbers, reals, rationals, algebraic extensions of rationals, p-adic numbers, or a finite field. Elliptic curves groups for cryptography are examined with the underlying fields of Fp (where is a prime) and F' (a binary representation with 2m elements
  12. General form of a EC An elliptic curve is a plane curve defined by an equation of the form Examples 3 —4x — x3 —x
  13. Weierstrass Equation A two variable equation F(x,y)=0, forms a curve in the plane. are seeking geornetric arithmetic methods to find solutions Generalized Weierstrass Equation of elliptic curves: y -k -k = X -k a2X -k a 4X -k a6 Here, A, B, x and y all belong to a field of say rational numbers, complex numbers, finite fields (Fp) or Galois Fields (GF(2n)).
  14. If Characteristic field is not 2: qx a = X -k a2X -k a 4X -k a6 If Characteristics of field is neither 2 nor 3:
  15. Points on the Elliptic Curve (EC) Elliptic Curve over field L It is useful to add the point at infinity The point is sitting at the top of the y-axis and any line is said to pass through the point when it is vertical It is both the top and at the bottom of the y-axis
  16. The Abelian Group Given two points P,Q in E(Fp), there is a third point, denoted by P+Qon E(Fp), and the following relations hold for all in E(Fp) commutativity associativity existence of an identity element) there exists ( — P) such that — = + ( — existence of inverses P)
  17. Elliptic Curve Picture Consider elliptic curve If p and P2 are on E, we can define 3 2 as shown in picture Addition is all we need
  18. Addition in Affine Co-ordinates -(13 + Q) Let, P*Q,
  19. Doubling of a point Let, dy — 3x2 -k A dx dy 3x12 -k A dx 2Yl If, O (since then Pl+P2=T): = m — 2X1, = m(X1 —XO — Yl What happens when Proo?
  20. Why do we need the reflection? P 00
  21. Sum of two points Define for two points P (XI,YI) and Q (X2,Y2) in the Elliptic curve -R x P (-2.35, -1.86) Q (-0.1, 0.836) -R (3.89, 5.62) R (3.89, -5.62) P + Q = R = (3.89, -5.62). for _ xl = 2Yl Then P+Q is given by : = I(X3 — + 2
  22. P (2, 2.65) -R (-1.11, -2.64) R (-1.11, 2.64) 2P (-1.11, 2.64). =x3-3x+5 Point at infinity As a result of the above case P=O+P O is called the additive identity of the elliptic curve group. Hence all elliptic curves have an additive identity O.
  23. Projective Co-ordinates Two-dimensional projective space p: over K is given by the equivalence classes of triples (x,y,z) with x,y z in K and at least one of x, y, z nonzero. Two triples (Xl and are said to be equivalent if there exists a non-zero element Å in K, St: — (Xl ,ZI) = (ÅX2, ÅY2, ÅZ2) — The equivalence class depends only the ratios and hence is denoted by (x:y:z)
  24. Projective Co-ordinates If (x:y:z)=(x/z:y/z:l) What is z=0? We obtain the point at infinity. The two dimensional affine plane over K: Hence using, There are advantages with projective co-ordinates from the implementation point of view
  25. Singularity For an elliptic curve define A singularity of the EC is a pt (xo,yo) such that: = — (xo, yo) = 0 Ox Dy or, 2 yo = —f '(xo) = 0 or, f (xo) = f '(xo) . f has a double root It is usual to assume the EC has no singular points
  26. If Characteristics of 1. 2. field is not 3: Hence condition for no singularity is 4A3+27B2*O Generally, EC curves have no singularity = —— (xo, yo) = 0 ax or, 2 yo = —f '(xo) = 0 or, f (xo) = f '(xo) . f has a double root For double roots, x3 -k AX B = 3x2 + = O Also, x4 -k AX2 4-BX=O, 9 3 2A2 9B 2A2 9B 4 A 3 + 27 B2 = O
  27. Elliptic Curves in Characteristic 2 Generalized Equation: y -k -k = X -k a2X -k a 4X -k 616 If al is not 0, this reduces to the form: y + XY = X3 + AX2 -k B If al is 0, the reduced form is: Note that the form cannot be:
  28. Outline of the Talk... Introduction to Elliptic Curves Elliptic Curve Cryptosystems Implementation of ECC in Binary Fields
  29. Elliptic Curve Cryptosystems (ECC)
  30. Public-Ke Sourcc Cr Message Source tos Decryption Algorithm stems Des/inati01i•.B Decryption Algorithm Encryption Algorithm Key Pair Source Encryption Algorithm Message KRbl IKey Pair Source Public-Key Cryptosystem: Secrec Authentication: Only A can generate the encrypted message an Authentication Secrecy: Only B can Decrypt the message
  31. Public-Ke Bobs's public key ring Ted Alice Aliceis public key O Cr Transmitted ciphertext to ra Joy Mike Plaintext h Alice Is private key o Plaintext Encryption algorithm input (eg„ RSA) Decryption algorithm output (reverse of encryption algorithm) (a) Encryption
  32. Public-Ke Bobis private key O Cr Transmitted ciphertext to ra h Alice's pu blie key ring Mike Ted Bob Bobls public key Plaintext Encryption algorithm input (eg., RSA) Plaintext Decn•ption algorithm output (reverse of encryption algorithm) (b) Authentication
  33. What Is Elliptic Curve Cryptography (ECC)? Elliptic curve cryptography [ECC] is a public- key cryptosystem just like RSA, Rabin, and El Gamal. Every user has a public and a private key. — Public key is used for encryption/signature verification. — Private key is used for decryption/signature generation. Elliptic curves are used as an extension to other current cryptosystems. — Elliptic Curve Diffie-Hellman Key Exchange — Elliptic Curve Digital Signature Algorithm
  34. Using Elliptic Curves In Cryptography The central part of any cryptosystem involving elliptic curves is the elliptic qroup. All public-key cryptosystems have some underlying mathematical operation. — RSA has exponentiation (raising the message or ciphertext to the public or private values) — ECC has point multiplication (repeated addition of two points).
  35. Generic Procedures of ECC Both parties agree to some publicly-known data items The elliptic curve equation values of a and b prime, p The elliptic qroup computed from the elliptic curve equation A base point, B, taken from the elliptic group Similar to the generator used in current cryptosystems Each user generates their public/private key pair Private Key = an integer, x, selected from the interval [1 , p-l] Public Key = product, Q, of private key and base point
  36. Example — Elliptic Curve Cryptosystem Analog to El Gamal Suppose Alice wants to send to Bob an encrypted message. — Both agree on a base point, B. — Alice and Bob create public/private keys. Alice — Private Key = a - Public Key PA = B Bob — Private Key = b - Public Key = = B — Alice takes plaintext message, M, and encodes it onto a point, PM, from the elliptic group
  37. Example — Elliptic Curve Cryptosystem Analog to El Gamal — Alice chooses another random integer, k from the interval [1 , p-l] — The ciphertext is a pair of points Pc = (kB), (PM + kPB) — To decrypt, Bob computes the product of the first point from Pc and his private key, b — Bob then takes this product and subtracts it from the second point from Pc , (PM + kPB) - [b(kB)] = PM + k(bB) - b(kB) = PM — Bob then decodes PM to get the message, M.
  38. Example — Compare to El Gamal — The ciphertext is a pair of points Pc = [ (kB), (PM + kPB) ] — The ciphertext in El Gamal is also a pair. C = (gk mod p, mPBk mod p) — Bob then takes this product and subtracts it from the second point from Pc , (PM + kPB) - [b(kB)] = PM + k(bB) - b(kB) = PM — In El Gamal, Bob takes the quotient of the second value and the first value raised to Bob's private value m = mPBk / (gk)b = mgk*b / gk*b = m
  39. Diffie-Hellman (DI-I) Key Exchange User A Generate random XA < q; Calculate Y A —u A mod q Calculate K — mod q 'User B Generate random < q; Calculate uXB mod q; Calculate K (YA)NBmod q
  40. ECC Diffie-Hellman Public: Elliptic curve and point on curve Secret: Alice's a and Bob's b a(x,y) b(x,y) Alice, A Alice computes a(b(x,y)) Bob computes b(a(x,y)) These are the same since ab Bob, B ba
  41. Example — Elliptic Curve Diffie-Hellman Exchange Alice and Bob want to agree on a shared key. — Alice and Bob compute their public and private keys. Alice Private Key = a Public Key PA = B Bob Private Key = b Public Key = = B — Alice and Bob send each other their public keys. — Both take the product of their private key and the other user's public key. Alice KAB — - a(bB) Bob K AB = b(aB) Shared Secret Key = KAB - abB
  42. Why use ECC? How do we analyze Cryptosystems? — How difficult is the underlying problem that it is based upon RSA— Integer Factorization DH — Discrete Logarithms ECC - Elliptic Curve Discrete Logarithm problem — How do we measure difficulty? We examine the algorithms used to solve these problems
  43. Security of ECC To protect a 128 bit AES key it would take a: NIST guidelines for public key sizes for AGS RSA Key Size: 3072 bits 163 - ECC Key Size: 256 bits 384 How do we 512 strengthen RSA? — Increase the key length Impractical? 3072 7680 15360 KEY RATIO 1:12 1120 1:30 128 192 256
  44. Applications of ECC Many devices are small and have limited storage and computational power Where can we apply ECC? — Wireless communication devices — Smart cards — Web servers that need to handle many encryption sessions — Any application where security is needed but lacks the power, storage and computational power that is necessary for our current cryptosystems
  45. Benefits of ECC Same benefits of the other cryptosystems: confidentiality, integrity, authentication and non-repudiation but... Shorter key lengths — Encryption, Decryption and Signature Verification speed up — Storage and bandwidth savings
  46. Summary of ECC Hard problem analogous to discrete log Q=kP, where Q, P belong to a prime curve given k, P "easy" to compute Q given Q, P "hard" to find k known as the elliptic curve logarithm problem k must be large enough ECC security relies on elliptic curve logarithm problem compared to factoring, can use much smaller key sizes than with RSA etc for similar security ECC offers significant computational advantages
  47. Outline of the Talk... Introduction to Elliptic Curves Elliptic Curve Cryptosystems Implementation of ECC in Binary Fields
  48. Implementation of ECC in Binary Fields
  49. 1. 2. 3. 4. 5. 6. 7. Sub-Topics Scalar Multiplication: LSB first vs MSB first Montgomery Technique of Scalar Multiplication Fast Scalar Multiplication without pre- computation. Lopez and Dahab Projective Transformation to Reduce Inverters Mixed Coordinates Parallelization Techniques Half and Add Technique for Scalar Multiplication
  50. ECC operations: Hierarchy Parallelize the architectures ECC point multiplication: Group operation: point add/double inite field arithmetic: multiplication, addition, subtraction, inversion, Level 0 Level 1 Level 2 Level 3
  51. Scalar Multiplication: MSB first Require k=(k k km-I m-l' m-2" Compute Q=kP — For i=m-2 to 0 , Q=2Q Sequential Algorithm If ki=l then Requires m point doublings and - Q=Q+P (m-l )/2 point additions on the , End if average - End for — Return Q
  52. Example Compute 7P: 11)2 — 7P=2(2(P)+P)+P=> 2 iterations are required — Principle: First double and then add (accumulate) Compute 6P:
  53. Scalar Multiplication: LSB first Require k=(k k m-l' m-2" Compute Q=kP - For to m-l If ki=l then - Q=Q+R , End if , R=2R - End for — Return Q km-I Can Parallelize What you are doubling and what you are accumulating are different... On the average m/2 point Additions and m/2 point doublings
  54. Example • Compute 7P - Q=7P, R=8P Compute 6P - R=4P
  55. Compute 31 P... MSB First 2. 3. 4. 5. 6. 7. 8. 2. 3. 4. 5. LSB First Q=P, R=2P Q=3P, R = 4p Q=7P, R Q=15p, R = 16p Q —31 p, R=32P
  56. Weierstrass Point Addition y 2 -I-xy = x3 + b, (x, y) G x Let, be a point on the curve. Let, 1. Point addition and doubling each require 1 inversion & 2 multiplications 2. We neglect the costs of squaring and addition Montgomery noticed that the 3. x-coordinate of 2P does not depend on the y-coordinate of
  57. Montgomery's method to perform scalar multiplication Input: k>O, P Output: Q=kP Set k ) l. 2. 3. 4. Set PI=P, P2=2P For i from 1-2 to 0 Set P - else Set P - Return Q=PI Invariant Property: p=ptpl 2 Question: How to implement the Operation efficiently? 1
  58. Example Compute 7P Initialization: p 1=p; P2=2P Steps: _ p 1=3P — PIZ7P Compute 6P Initialization: p 1=p; P2=2P Steps: _ p 1=3P, P2=4P _ P2=7P, PI
  59. Fast Multiplication on EC without pre-computation
  60. Result-I Let PI = (Xl ,YI) and be elliptic points. Then the x-coordinate of Pl+P2, can be computed as: 2 XlY2 -k X2Y1 -l- XlX2 -k X2X1 (Xl + X2)2 Hint: Remember that the field has a characteristic 2 and that PI and P2 are points on the curve
  61. Result-2 Let PI = (XI,YI) and be elliptic points. Let p=pzpl be an invariant. Then the x-coordinate of Pl+P2, can be computed in terms of the x-coordinates as:
  62. Result-3 Let and be elliptic points. Assume that and x is not 0. Then the y-coordinates of PI can be expressed in terms of P, and the x-coordinates of PI and P2 as follows:
  63. Final Algorithm Input: k>0, P=(x,y) Output: Q=kP If or then output(0,0) 2. 3. 4. 5. 6. 7. Set k = (k k I-I' 1-2, Set -x, xrx2+b/x2 For i from 1-2 to 0 1. Set 2. If ki=l, else Return ,YI) , #MULT: , #ADD: , #SQR:
  64. 2. 3. How to reduce inversions? In affine coordinates Inverses are very expensive For 112128 each inversion requires around 7 multipliers (in hardware designs) Lopez Dahab Projective coordinates æo, maps to (X/Z,Y/Z2) Motivation is to replace inversions by the multiplication operations and then perform one inversion at the end (to obtain back the affine coordinates)
  65. Remember: Doubling X12 + . ; Pl In Projective Coordinates: PI # P2, 4 - (Xl.Z2 + X2.Zl)2 x.Z3 4) 2 inverses 1 general field multiplication 4 additions 2 squarings 0 inverses 4 general field multiplications 3 additions 5 squarings
  66. Montgomery Algorithm Input: k>0, P=(x,y) Output: Q=kP Set k ) Set & ; xrx4+b, For i from 1-2 to 0 Madd(Xl else ,ZO, MdoubIe(Xl Return
  67. Mxy: Projective to Affine Requires 10 multiplications and one inverse operation
  68. Final Comparison Affine Coordinates Inv: 210gk + 1 Mult: 210gk + 4 Add: 410gk + 6 sqr: + 2 Projective Coordinates Mult: 610gk + 10 Add: 310gk + 7 sqr: 510gk + 3 Hence, final decision depends upon the ratio of the finite field operators
  69. Addition in Mixed Coordinates Theorem: Let ,Yl/Z12) and be two points on the curve. If , then st. U +Y2,s +X2,T = Y3 = (V + +4) +Z32c Number of multiplications are further reduced Squaring is increased a bit, but they are cheap in GF(2n) Improvement by 10 % if otherwise 12 0/0..
  70. Parallel Strategies for Scalar Point Multiplication Point Doubling - cycle I : T=X12, M=cZ12, Z2=T.Z12 - cycle la: Point Addition - cycle I : .Z2); .X2) - cycle la: 4=M2 1 multiplier 2 multipliers - cycle 2: N=tl.t2, - cycle 2a: XI=M+N We assume that squarings and multiplications With constants can be performed without multipliers.a.
  71. Parallelizing Montgomery Algorithm 2. 3. 4. 5. 6. Input: k>0, P=(x,y) Output: Q=kP Set k ) Set & ; xrx4+b, For i from 1-2 to 0 else 5b) Return
  72. Parallelize the architectures Looking back at our Design Hierarchy ECC point multiplication: Group operation: point add/double inite field arithmetic: multiplication, addition, subtraction, inversion, Level 0 Level 1 Level 2 Level 3
  73. Parallelizing Strategies Parallelize level 1: If we allocate one multiplier to each of Madd and Mdouble, then we can parallelize steps 5a and 5b. Thus 4 clock cycles are required for each iteration. Total time is nearly Parallelize level 2: If we can parallelize the underlying Madd and Mdouble, then we cannot parallelize level 1, if we have constraint of 2 multipliers. So, we have a sequential step 5a and 5b. Total time is 31.
  74. Parallelizing Strategies Parallelize both the levels: Total time is 2/ clock cycles. Require 3 multipliers. Thus Montgomery algorithm is highly parallelizable Helpful in high performance designs (low power, high thoughput etc
  75. Point Halving In 1999 Scroeppel and Knudsen proposed further speed up Idea is to replace point doubling by halving Point Halving is three times as fast than doubling The scalar k, has to be expressed in the negative powers of 2
  76. Computing the Half Problem: Let E be the Elliptic Curve, defined by the equation: Let Compute P=(x,y) Remember : b x x
  77. Halving (contd.) Let , Z = x — x V + (Z + 1)bl Note : 12 + = u -k a Thus, we have to solve the above equations Å-representation: (x, Åx) Square Root Solving Quadratics
  78. Trace of a point Define: Tr(C) = C+ C2 + C2 Properties of Trace: - Tr(c) can be O or I - NIST Curves : — If x,y belongs to the Elliptic Curve, Tr(x)=Tr(a)
  79. Computing The roots of 12 +1=u+a are Å or Å+I Theorem: Let, P = (x, (u,v) G, st. Q = 2P and denote 1 = x + y / x. Let 1 be a solution to 12 +1 = u + a and t = v + uh. Suppose that Tr(a) = 1. Then 1 = 1 if and only if Tr(t) = 0.
  80. 1. 2. 3. 4. Halving Algorithm Input: (u,v) , Output: (x,y) for Let the root be i Solve 12 + + a Compute t=v+uÄ If Tr(t)=0, then Åp=i , else +1 Return (x,Åp)
  81. Implementation of Trace m—l m—l Trace : Tr(C) = qxl) = E CiTr(f) i=0 i=0 Can be evaluated in 0(1) time Example: GF(2163), with reduction polynomial , , iff or 159. Thus, the implementation is only gate one xor to add the 0th and the 159th bits of the register storing C.
  82. Solving a Quadratic over GF(2m) Solve x2+x=c+Tr(c), c is an element of GF(2m) Define Half Trace: On-1)/2 221 2. H(C) is a root for + x = C+Tr(C), as H(C) gives a root for the quadratic equation. A simple method to find H(C) requires storage for m elements and m/2 field additions on an average
  83. Obtaining Square Root Field squaring in binary field is linear Hence squaring can be rephrased as: We require to compute D st. D2=A A-MD Let, D2=MD (as M is the squaring matrix) , Hence,
  84. An Example 763R , where order of R =1013 Compute: m = 10 210 1(763) - 651(mod 1013) = (1010001011)2 . 763 = + — + — -k — -k 1) mod(1013) 29 28 26 22 763R7 may be computed using the following steps: Step 1: 11 Step 2 22 Step 3: Similarly continue...
  85. 2. 3. 4. 5. 6. Half and Add Algorithm Input: 0
  86. Key References Papers: — J. Lopez and R. Dahab, "Fast Multiplication on Elliptic Curves over GF(2m) without pre-computation", CHES 1999 - K. Fong etal, "Field Inversion and Point Halving Revisited", IEEE Trans on Comp, 2004 G. Orlando and C. Paar, "A High Performance Reconfigurable Elliptic Curve Processor for GF(2m)", CHES 2000 — N. A. Saqib etal, "A Parallel Architecture for Fast Computation of Elliptic Curve Scalar Multiplication over GF(2m)", Elsevier Journal of Microprocessors and Microsystems, 2004 — Sabiel Mercurio etal, "An FPGA Arithmetic Logic Unit for Computing Scalar Multiplication using the Half-and-Add Method" IEEE Reconfig 2005
  87. Key References , Books: — Elliptic Curves: Number Theory and Cryptography, by Lawrence C. Washington — Guide to Elliptic Curve Cryptography, Alfred J. Menezes — Guide to Elliptic Curve Cryptography, Darrel R. Hankerson, A. Menezes and A. Vanstone — http://cr.yp.to/ecdh.html ( Daniel Bernstein)
  88. Thank You

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related PPTs

Upload PPTs

If you have your own PowerPoint Presentations which you think can benefit others, please upload on LearnPick. For each approved PPT you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > PowerPoint Slides > X-Ray Diffraction