| Koblitz exponentiation with bucketing -> Monitor Keywords |
|
|
  Koblitz exponentiation with bucketingUSPTO Application #: 20080044013Title: Koblitz exponentiation with bucketing Abstract: An implementation of a technology, described herein, for facilitating cryptographic systems and techniques. At least one implementation, described herein, maximizes the speed and security of fast exponentiation while minimizing its expense. At least one implementation, described herein, employs elliptic curves with a fast exponentiation technique so that it maximizes speed and security while minimizing expense. At least one implementation, described herein, employs Koblitz exponentiation with “bucketing” techniques to maximize speed and security of cryptosystems while minimizing expense of such techniques. This abstract itself is not intended to limit the scope of this patent. The scope of the present invention is pointed out in the appending claims. (end of abstract) Agent: Lee & Hayes PLLC - Spokane, WA, US Inventors: Peter L. Montgomery, Kristin Estella Lauter USPTO Applicaton #: 20080044013 - Class: 380 30 (USPTO) The Patent Description & Claims data below is from USPTO Patent Application 20080044013. Brief Patent Description - Full Patent Description - Patent Application Claims
RELATED APPLICATIONS [0001]This continuation application claims priority to U.S. patent application Ser. No. 10/184,737 to Montgomery et al, entitled, "Koblitz Exponentiation with Bucketing," filed Jun. 27, 2002. TECHNICAL FIELD [0002]This invention generally relates to a technology for facilitating cryptographic systems and techniques. BACKGROUND [0003]Cryptographic systems--such as those of the Public-Key Infrastructure (PKI)--often involve raising elements of some group to large powers. Examples of groups include the symmetries of a geometrical object, the integers modulo a is positive integer N under addition (Z/NZ), and elliptic curves. The task of raising elements of some group to (possibly) large powers is called "exponentiation". Exponentiation is a central and expensive part of many cryptographic protocols. [0004]Mathematically, exponentiation may be described as thus: Let G be a group with multiplicative operator {circle around (.times.)}. Given g .epsilon. G and an integer n, compute g.sup.n. The meaning of g.sup.n may be found in abstract algebra books. When n>0, it denotes the product g{circle around (.times.)}g{circle around (.times.)}g{circle around (.times.)} . . . {circle around (.times.)}g, with n copies of g being multiplied together (thus n-1 applications of {circle around (.times.)}). The definition of group requires {circle around (.times.)} to be associative. This exponentiation obeys the algebraic laws g.sup.m{circle around (.times.)}g.sup.n=g.sup.m+n and (g.sup.m).sup.n=g.sup.mn for arbitrary integers m and n. Within an abelian (=commutative) group or subgroup (the case of interest herein) exponentiation also satisfies (g{circle around (.times.)}h).sup.n=g.sup.n{circle around (.times.)}h.sup.n. [0005]Three common exponentiation scenarios: [0006]g is fixed and n varies (e.g., first phase of Diffie-Hellman); [0007]g varies and n is fixed (e.g., RSA); [0008]both g and n vary (e.g., second phase of Diffie-Hellman). [0009]Generally, the security of a cryptographic system is based, at least in part, on exponentiation being difficult to invert. That means that it is extraordinarily difficult to determine the original operands based upon the results of such exponentiation. The discrete logarithm problem tries to find n given g and g.sup.n. The Diffie-Hellman protocol uses groups in which this problem is believed to be hard. Other protocols may employ groups of unknown order (-number of elements), in which case it may be hard to find g given n and g.sup.n. [0010]The following references discuss various exponentiation techniques (particularly those in relation to cryptography): [0011]Donald E. Knuth, "The Art of Computer Programming", Volume 2, Seminumerical Algorithms, 3rd edition, Addison-Wesley, 1997. [0012]IEEE Standard Specifications for Public-Key Cryptography, IEEE Std 1363-2000, IEEE Computer Society, 29 Aug. 2000. Some Mathematical Notation Used Herein [0012] [0013]B.sub.j Contents of bucket j, typically the product of several items related to the subscript j. [0014]C.sub.w For fixed w, a fixed subset of Z[.tau.] containing small-norm representatives of certain residue classes modulo .tau..sup.w. [0015]ceil(x) Ceiling function: the least integer n such that n.gtoreq.x, where x is real. [0016]E An elliptic curve equation. [0017]E.sub.a,b The elliptic curve y.sup.2+xy=x.sup.3+ax.sup.2+b over a field of characteristic 2. [0018]floor(x) Floor function: the largest integer n such that n.ltoreq.x, where x is real. [0019]GF(q) Field with q elements, where q is a prime or prime power. [0020]I Identity function (I(P)=P for all P), on elliptic curve group. [0021]log.sub.2(x) Real base 2 logarithm of x, where x is real, x>0. [0022]m An integer. Used for extension degree in GF(2.sup.m). [0023].mu.(-1).sup.a+1 where a is taken from elliptic curve equation (EK). [0024]n An integer, usually an exponent. [0025]p A prime. [0026]P Point on an elliptic curve. [0027]Q Field of rational numbers. [0028]Q(.tau.) Field generated by .tau.. Contains all a+b.tau. where a, b .epsilon. Q. [0029]T.sub.frob Frobenius endomorphism: T.sub.frob ((x, y))=(x.sup.p, y.sup.p). [0030]T An endomorphism on Koblitz curves, satisfying T.sup.2-T+2I=O. Same as .mu.T.sub.frob. [0031].tau. An algebraic integer, specifically one satisfying .tau..sup.2-.tau.+2=0. [0032]Z Ring of integers. [0033]Z[.tau.] Ring of integers generated by .tau.. Contains all a+b.tau. where a, b .epsilon. Z. [0034]O Identity element (point at infinity) in an elliptic curve group. [0035]+, -, .+-. Addition and subtraction operators in elliptic curve group. [0036]{circle around (.times.)} Multiplication operator in abstract group. Fast Exponentiation [0037]Often, the speed of an exponentiation determines its practicality. Various factors affect the speed and efficiency of exponentiation. Such factors include: which group or other algebraic system is being used, the hardware the system is implemented on, and whether one element is repeatedly being raised to different powers, different elements are raised to a fixed power, or both the powers and the base elements vary. Binary Techniques of Exponentiation [0038]Many of the binary techniques of exponentiation are well-known to those of ordinary skill in the art. They are explained in references (cited above). [0039]Let x be an element of a multiplicative group (or a semigroup) with operator {circle around (.times.)} and let n be a positive integer. The problem is to compute x.sup.n while minimizing the number of multiplications. Herein, squarings (in which one knowingly multiplies an element by itself) are distinguished from other multiplications. For the sake of clarity and simplicity, the description, herein, assumes the time per multiplication (or squaring) is independent of the values being multiplied (or squared). [0040]A naive technique successively computes x.sup.2=x{circle around (.times.)}x , x.sup.3=x.sup.2{circle around (.times.)}x, x.sup.4=x.sup.3{circle around (.times.)}x, . . . , x.sup.n=x.sup.n-1{circle around (.times.)}x. This takes n-1 group multiplications. It is acceptable for small n (e.g., n<20) but totally impractical when the exponent has 100 or more bits, as may happen in cryptographic applications. [0041]Fortunately, one may lower the operation count from O(n) to O(log.sub.2(n)) using associativity. For example, one may skip the computation of x.sup.3 and proceed directly to x.sup.4=x.sup.2{circle around (.times.)}x.sup.2. The square-and-multiply technique, also called the left-to-right binary technique, uses at most floor(log.sub.2(n)) squarings and floor(log.sub.2(n)) additional multiplications. One may implement it by scanning the binary representation of n. [0042]For example, if n = 1234567 = 1048576 + 131072 + 32768 + 16384 + 4096 + 1024 + 512 + 128 + 4 + 2 + 1 = ( 100101101011010000111 ) 2 , Continue reading... Full patent description for Koblitz exponentiation with bucketing Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Koblitz exponentiation with bucketing patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Koblitz exponentiation with bucketing or other areas of interest. ### Previous Patent Application: Vehicular holding module capable of zooming information displayed on a screen Next Patent Application: Reducing security protocol overhead in low data rate applications over a wireless link Industry Class: Cryptography ### FreshPatents.com Support Thank you for viewing the Koblitz exponentiation with bucketing patent info. IP-related news and info Results in 1.51953 seconds Other interesting Feshpatents.com categories: Qualcomm , Schering-Plough , Schlumberger , Seagate , Siemens , Texas Instruments , |
||
