For more than a decade, the separate fields of legislation and cryptography have contributed to the development of electronic signatures from divergent perspectives. Research on legislation establishes the legal requirements for electronic signatures, which have been stipulated in legislative frameworks. Research on cryptography mainly focuses on the development of algorithms to enhance the security and efficiency of the methods adopted to generate electronic signatures, for instance, cryptographic signature schemes. This research draws together the knowledge from both of these fields and takes an integrated approach to assess whether a signature scheme is capable of generating electronic signatures satisfying the legal requirements. This research first identifies and consolidates the legal requirements for electronic signatures in three commonly used legislative frameworks. Based on these requirements, an assessment mechanism called LCD assessment is formalized to evaluate the eligibility of signature schemes in generating legally recognized electronic signatures. Results show that when the LCD assessment is applied to several provably secure signature schemes, one of these schemes does not adequately satisfy the assessment. This significant finding suggests that even a provably secure signature scheme is not necessarily capable of generating legally recognized electronic signatures. Furthermore, electronic signature legislation has been promulgated in many countries. Due to variations in legislation, countries enforce different regulations and divergent standards for electronic signatures. Such enforcement will prevent an electronic signature from being used across the border if the signature cannot simultaneously fulfill multiple regulatory requirements and standards. This issue creates the interoperability problem of public key infrastructure (PKI). Several major countries have attempted to address this problem through adopting different interoperability models. These models are analyzed in this study and the results suggest that the models can only achieve PKI interoperability at a regional level. A new unified PKI framework is proposed with a vision to enhance the PKI interoperability through harmonizing the practices and standards at an international level. Such a framework not only addresses the technical issues for electronic signatures, but also eliminates the legal uncertainties of the use of signature schemes through incorporating the LCD assessment. The outcomes of this research are therefore twofold. First, the LCD assessment provides a mechanism to assess the eligibility of signature schemes from a legal perspective. Second, the new unified PKI framework begins to resolve the issues in cross-border use of electronic signatures through a multi-discipline approach. In addressing the interaction between legislation and technology for electronic signatures, the wider use of electronic signatures in global electronic commerce is envisaged. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Wong, Chun Kuen. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 43-45). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Origin of The First Digital Signature Scheme --- p.2 / Chapter 1.2 --- On the security of digital signature schemes --- p.3 / Chapter 1.3 --- Organization of the Thesis --- p.4 / Chapter 2 --- Mathematical Background --- p.6 / Chapter 2.1 --- Divisibility --- p.6 / Chapter 2.2 --- Prime --- p.7 / Chapter 2.3 --- Modular arithmetic --- p.7 / Chapter 2.4 --- Congruence --- p.7 / Chapter 2.5 --- Greatest Common Divisor --- p.7 / Chapter 2.6 --- Integers modulo n --- p.8 / Chapter 2.7 --- Inverse --- p.8 / Chapter 2.8 --- Division in Zn --- p.8 / Chapter 2.9 --- Order of element --- p.8 / Chapter 2.10 --- Euclidean Algorithm --- p.9 / Chapter 2.11 --- Extended Euclidean Algorithm --- p.9 / Chapter 2.12 --- Chinese Remainder Theorem --- p.10 / Chapter 2.13 --- Relatively Prime --- p.10 / Chapter 2.14 --- Euler Totient Function --- p.10 / Chapter 2.15 --- Fermat's Little Theorem --- p.11 / Chapter 2.16 --- Euler's Theorem --- p.11 / Chapter 2.17 --- Square root --- p.12 / Chapter 2.18 --- Quadratic residue --- p.12 / Chapter 2.19 --- Legendre Symbol --- p.13 / Chapter 2.20 --- Jacobi Symbol --- p.14 / Chapter 2.21 --- Blum Integer --- p.15 / Chapter 2.22 --- The Factoring Problem --- p.16 / Chapter 2.23 --- The Discrete Logarithm Problem --- p.17 / Chapter 2.24 --- One-way Hash Function --- p.17 / Chapter 3 --- Survey of digital signature schemes --- p.19 / Chapter 3.1 --- The RSA signature scheme --- p.19 / Chapter 3.1.1 --- Key generation in the RSA signature scheme --- p.20 / Chapter 3.1.2 --- Signature generation in the RSA signature scheme --- p.20 / Chapter 3.1.3 --- Signature verification in the RSA signature scheme --- p.20 / Chapter 3.1.4 --- On the security of the RSA signature scheme --- p.21 / Chapter 3.2 --- The ElGamal signature scheme --- p.22 / Chapter 3.2.1 --- Key generation in the ElGamal signature scheme --- p.23 / Chapter 3.2.2 --- Signature generation in the ElGamal signature scheme --- p.23 / Chapter 3.2.3 --- Signature verification in the ElGamal signature scheme --- p.23 / Chapter 3.2.4 --- On the security of the ElGamal signature scheme --- p.24 / Chapter 3.3 --- The Schnorr signature scheme --- p.26 / Chapter 3.3.1 --- Key generation in the Schnorr signature scheme --- p.26 / Chapter 3.3.2 --- Signature generation in the Schnorr signature scheme --- p.26 / Chapter 3.3.3 --- Signature verification in the Schnorr signature scheme --- p.27 / Chapter 3.3.4 --- Discussion --- p.27 / Chapter 3.4 --- Digital signature schemes based on both the factoring and discrete logarithm problems --- p.27 / Chapter 3.4.1 --- The Brickell-McCurley signature scheme --- p.28 / Chapter 3.4.2 --- The Okamoto signature scheme --- p.29 / Chapter 3.4.3 --- The Harn signature scheme --- p.30 / Chapter 3.4.4 --- The Shao signature scheme --- p.30 / Chapter 3.4.5 --- The W. He signature scheme --- p.31 / Chapter 4 --- Cryptanalysis of the digital signature scheme of W. He --- p.32 / Chapter 4.1 --- The Digital Signature Scheme of W. He --- p.33 / Chapter 4.1.1 --- System setup in the W. He Digital Signature Scheme --- p.33 / Chapter 4.1.2 --- Key generation in the W. He Digital Signature Scheme --- p.34 / Chapter 4.1.3 --- Signature generation in the W. He Digital Signature Scheme --- p.34 / Chapter 4.1.4 --- Signature verification in the W. He Digital Signature Scheme --- p.34 / Chapter 4.2 --- Cryptanalysis of the digital signature scheme of W. He --- p.35 / Chapter 4.2.1 --- Theorems on the security of the digital signature scheme of W. He --- p.35 / Chapter 4.2.2 --- Signature Forgery in the digital signature scheme of W. He --- p.37 / Chapter 4.2.3 --- Remedy --- p.40 / Chapter 5 --- Conclusions --- p.41 / Bibliography --- p.43

by Wah-Kit Chan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 84-87). / Abstracts in English and Chinese. / Acknowledgement --- p.i / Abstract of thesis entitled: --- p.ii / 摘要 --- p.iii / List of Tables --- p.vii / List of Figures --- p.viii / Chapter 1. --- Introduction --- p.1 / Chapter 1.1 --- Preview of this thesis --- p.1 / Chapter 1.1.1 --- What is Signcryption? --- p.2 / Chapter 1.1.2 --- What is Proxy? --- p.2 / Chapter 1.1.3 --- What is Threshold? --- p.2 / Chapter 1.2 --- Development Timelines --- p.3 / Chapter 1.3 --- Recent progress on signcryption --- p.4 / Chapter 1.4 --- Organization of this thesis --- p.5 / Chapter 2. --- Introduction to Cryptography --- p.6 / Chapter 2.1 --- Cryptographic Primitives --- p.7 / Chapter 2.1.1 --- Symmetric Cryptography --- p.7 / Chapter 2.1.2 --- Asymmetric Cryptography --- p.8 / Chapter 2.1.3 --- Digital Signature --- p.8 / Chapter 2.1.4 --- Hash Function --- p.9 / Chapter 2.1.5 --- Digital Certificate --- p.10 / Chapter 2.1.6 --- Zero Knowledge Proof --- p.10 / Chapter 2.2 --- Discrete Logarithm Based Crypto system --- p.11 / Chapter 2.2.1 --- ElGamal Public and Private Key Generation Algorithm --- p.11 / Chapter 2.2.2 --- ElGamal Encryption Algorithm --- p.12 / Chapter 2.2.3 --- ElGamal Decryption Algorithm --- p.12 / Chapter 2.3 --- Integer Factorization Based Cryptosystem --- p.13 / Chapter 2.3.1 --- RSA Public and Private Key Generation algorithm --- p.13 / Chapter 2.3.2 --- RSA Encryption Algorithm --- p.14 / Chapter 2.3.3 --- RSA Decryption Algorithm --- p.14 / Chapter 2.4 --- Digital Signature --- p.14 / Chapter 2.4.1 --- RSA based Digital Signature --- p.15 / Chapter 2.4.2 --- ElGamal Digital Signature Scheme --- p.16 / Chapter 2.4.3 --- Digital Signature Standard --- p.17 / Chapter 2.4.4 --- Shortened Digital Signature Scheme --- p.20 / Chapter 2.4.5 --- Nyberg-Rueppel Digital Signature Scheme --- p.20 / Chapter 2.4.6 --- Schnorr Digital Signature Scheme --- p.21 / Chapter 2.5 --- Diffie-Hellman Key Exchange --- p.22 / Chapter 2.6 --- Blind Signature --- p.23 / Chapter 2.6.1 --- Overview --- p.23 / Chapter 2.6.2 --- Blinded Nyberg-Rueppel Digital Signature Scheme --- p.23 / Chapter 2.6.3 --- Discussion on Blind Signature Scheme --- p.24 / Chapter 2.7 --- Threshold Scheme --- p.24 / Chapter 2.7.1 --- Secret Sharing Scheme --- p.25 / Chapter 2.7.2 --- Petersen's Verifiable Secret Sharing Scheme --- p.26 / Chapter 3. --- Introduction to Signcryption --- p.27 / Chapter 3.1 --- "Traditional ""Signature-then-Encryption"" Scheme" --- p.28 / Chapter 3.1.1 --- Signature-then-Encryption based on RSA --- p.28 / Chapter 3.1.2 --- Signature-then-Encryption based on DSS + ElGamal Encryption --- p.29 / Chapter 3.1.3 --- Signature-then-Encryption based on Schnorr signature + ElGamal encryption --- p.30 / Chapter 3.2 --- Zheng's Digital Signcryption Scheme --- p.31 / Chapter 3.3 --- Proxy Signcryption Scheme --- p.32 / Chapter 3.4 --- Improved Digital Signcryption Scheme --- p.34 / Chapter 4. --- A Threshold Signcryption Scheme --- p.36 / Chapter 4.1 --- "A(t, n)-Threshold Signcryption Scheme" --- p.36 / Chapter 4.1.1 --- Scheme Description --- p.37 / Chapter 4.1.2 --- Validity Analysis --- p.40 / Chapter 4.1.3 --- Security Analysis --- p.43 / Chapter 4.2 --- "A (n, n)-Threshold Signcryption Scheme with Improved Complexity" --- p.45 / Chapter 4.2.1 --- Scheme Description --- p.45 / Chapter 4.2.2 --- Validity Analysis --- p.48 / Chapter 4.2.3 --- Security Analysis --- p.50 / Chapter 5. --- A Threshold Proxy Signcryption Scheme --- p.51 / Chapter 5.1 --- "A (t, n)-Threshold Proxy Signcryption Scheme" --- p.52 / Chapter 5.1.1 --- Scheme Description --- p.52 / Chapter 5.1.2 --- Validity Analysis --- p.57 / Chapter 5.1.3 --- Security Analysis --- p.59 / Chapter 5.2 --- "A (n, n)-Threshold Proxy Signcryption Scheme with Improved Complexity" --- p.61 / Chapter 5.2.1 --- Scheme Description --- p.61 / Chapter 5.2.2 --- Validity Analysis --- p.64 / Chapter 5.2.3 --- Security Analysis --- p.65 / Chapter 6. --- A Non-Repudiated Threshold Proxy Signcryption Scheme --- p.67 / Chapter 6.1 --- Non-repudiated Proxy Shares Generation --- p.68 / Chapter 6.2 --- Rushing Attack --- p.70 / Chapter 6.3 --- Non-repudiated and Un-cheatable Proxy Shares Generation --- p.72 / Chapter 6.4 --- "An Un-cheatable and Non-repudiated (t, n) Threshold Proxy Signcryption" --- p.76 / Chapter 6.4.1 --- Scheme Description --- p.76 / Chapter 6.4.2 --- Validity Analysis --- p.78 / Chapter 6.4.3 --- Security Analysis --- p.79 / Chapter 7. --- Conclusions --- p.81 / Appendix --- p.83 / Papers Derived from this thesis: --- p.83 / Bibliography --- p.84

Often we are less concerned with 'who' signed something than with 'what' attributes (director of this company etc.) they have. We propose three Attribute Based Signature schemes, namely, Decentralised Traceable Attribute Based Signatures (DTABS), Attribute Based Signatures with User-Controlled Linkability (ABS-UCL), and Attribute Based Signatures with Hidden Expressive Policy (ABS-HEP). The 'Traceability' assures that signatures in dispute, caused by any misuse/abuse cases, can be traced back to their signers. The judge of public opinion guarantees that no misattribution (framing) can take place. Additionally, 'User-Controlled Linkability' gives a lightweight solution to session-style ABS; signers can 'choose' to link some of their signatures that are directed to the same verifier, and the verifier will be convinced that those signatures are signed by the same anonymous person. %have the option to open a session with the same anonymous signer, whereas any signer has the capability to convince a given verifier that a series of signatures directed to it are all signed by the same person. 'Hidden expressive policy' gives the organizations the flexibility to change their signing policies without notifying the outside. All the three schemes are given and proven generically in a modular way. Instantiations for the first two schemes are also given to show both feasibility and practicality of the proposed schemes. The first two schemes substantially improve the state-of-the-art of Attribute Based Signatures that use Bilinear maps as a building block and shape it into a practical form, offering a 'decentralized' version of ABS where multiple authorities are involved and yet no reliance on a central authority is needed. In the third scheme, we move ABS into a new stage, where we increase the level of expressiveness of the signing policies to use general circuits, and at the same time, we give the signer the ability to fully hide his signing policy. This scheme makes use of hardness assumptions on the newly realized cryptographic building block, i.e. Multilinear maps.

Tsang Pak Kong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 95-107). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Privacy --- p.1 / Chapter 1.2 --- Cryptography --- p.5 / Chapter 1.2.1 --- History of Cryptography --- p.5 / Chapter 1.2.2 --- Cryptography Today --- p.6 / Chapter 1.2.3 --- Cryptography For Privacy --- p.7 / Chapter 1.3 --- Thesis Organization --- p.8 / Chapter 2 --- Background --- p.10 / Chapter 2.1 --- Notations --- p.10 / Chapter 2.2 --- Complexity Theory --- p.11 / Chapter 2.2.1 --- Order Notation --- p.11 / Chapter 2.2.2 --- Algorithms and Protocols --- p.11 / Chapter 2.2.3 --- Relations and Languages --- p.13 / Chapter 2.3 --- Algebra and Number Theory --- p.14 / Chapter 2.3.1 --- Groups --- p.14 / Chapter 2.3.2 --- Intractable Problems --- p.16 / Chapter 2.4 --- Cryptographic Primitives --- p.18 / Chapter 2.4.1 --- Public-Key Encryption --- p.18 / Chapter 2.4.2 --- Identification Protocols --- p.21 / Chapter 2.4.3 --- Digital Signatures --- p.22 / Chapter 2.4.4 --- Hash Functions --- p.24 / Chapter 2.4.5 --- Zero-Knowledge Proof of Knowledge --- p.26 / Chapter 2.4.6 --- Accumulators --- p.32 / Chapter 2.4.7 --- Public Key Infrastructure --- p.34 / Chapter 2.5 --- Zero Knowledge Proof of Knowledge Protocols in Groups of Unknown Order --- p.36 / Chapter 2.5.1 --- The Algebraic Setting --- p.36 / Chapter 2.5.2 --- Proving the Knowledge of Several Discrete Logarithms . --- p.37 / Chapter 2.5.3 --- Proving the Knowledge of a Representation --- p.38 / Chapter 2.5.4 --- Proving the Knowledge of d Out of n Equalities of Discrete Logarithms --- p.39 / Chapter 2.6 --- Conclusion --- p.42 / Chapter 3 --- Related Works --- p.43 / Chapter 3.1 --- Introduction --- p.43 / Chapter 3.2 --- Group-Oriented Signatures without Spontaneity and/or Anonymity --- p.44 / Chapter 3.3 --- SAG Signatures --- p.46 / Chapter 3.4 --- Conclusion --- p.49 / Chapter 4 --- Linkable Ring Signatures --- p.50 / Chapter 4.1 --- Introduction --- p.50 / Chapter 4.2 --- New Notions --- p.52 / Chapter 4.2.1 --- Accusatory Linking --- p.52 / Chapter 4.2.2 --- Non-slanderability --- p.53 / Chapter 4.2.3 --- Linkability in Threshold Ring Signatures --- p.54 / Chapter 4.2.4 --- Event-Oriented Linking --- p.55 / Chapter 4.3 --- Security Model --- p.56 / Chapter 4.3.1 --- Syntax --- p.56 / Chapter 4.3.2 --- Notions of Security --- p.58 / Chapter 4.4 --- Conclusion --- p.63 / Chapter 5 --- Short Linkable Ring Signatures --- p.64 / Chapter 5.1 --- Introduction --- p.64 / Chapter 5.2 --- The Construction --- p.65 / Chapter 5.3 --- Security Analysis --- p.68 / Chapter 5.3.1 --- Security Theorems --- p.68 / Chapter 5.3.2 --- Proofs --- p.68 / Chapter 5.4 --- Discussion --- p.70 / Chapter 5.5 --- Conclusion --- p.71 / Chapter 6 --- Separable Linkable Threshold Ring Signatures --- p.72 / Chapter 6.1 --- Introduction --- p.72 / Chapter 6.2 --- The Construction --- p.74 / Chapter 6.3 --- Security Analysis --- p.76 / Chapter 6.3.1 --- Security Theorems --- p.76 / Chapter 6.3.2 --- Proofs --- p.77 / Chapter 6.4 --- Discussion --- p.79 / Chapter 6.5 --- Conclusion --- p.80 / Chapter 7 --- Applications --- p.82 / Chapter 7.1 --- Offline Anonymous Electronic Cash --- p.83 / Chapter 7.1.1 --- Introduction --- p.83 / Chapter 7.1.2 --- Construction --- p.84 / Chapter 7.2 --- Electronic Voting --- p.85 / Chapter 7.2.1 --- Introduction --- p.85 / Chapter 7.2.2 --- Construction . --- p.87 / Chapter 7.2.3 --- Discussions --- p.88 / Chapter 7.3 --- Anonymous Attestation --- p.89 / Chapter 7.3.1 --- Introduction --- p.89 / Chapter 7.3.2 --- Construction --- p.90 / Chapter 7.4 --- Conclusion --- p.91 / Chapter 8 --- Conclusion --- p.92 / A Paper Derivation --- p.94 / Bibliography --- p.95

Chan Kwok Leong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 72-78). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Preliminaries --- p.4 / Chapter 2.1 --- Notation --- p.4 / Chapter 2.2 --- Cryptographic Primitives --- p.5 / Chapter 2.2.1 --- Symmetric Key Cryptography --- p.5 / Chapter 2.2.2 --- Asymmetric Key Cryptosystem --- p.6 / Chapter 2.2.3 --- Secure Hash Function --- p.7 / Chapter 2.2.4 --- Digital Signature --- p.8 / Chapter 2.2.5 --- Digital Certificate and Public Key Infrastructure --- p.8 / Chapter 2.3 --- Provable Security and Security Model --- p.9 / Chapter 2.3.1 --- Mathematics Background --- p.9 / Chapter 2.3.2 --- One-Way Function --- p.10 / Chapter 2.3.3 --- Candidate One-way Functions --- p.12 / Chapter 2.4 --- Proof Systems --- p.15 / Chapter 2.4.1 --- Zero-knowledge Protocol --- p.15 / Chapter 2.4.2 --- Proof-of-Knowledge Protocol --- p.17 / Chapter 2.4.3 --- Honest-Verifier Zero-Knowledge (HVZK) Proof of Knowl- edge Protocols (PoKs) --- p.18 / Chapter 2.5 --- Security Model --- p.19 / Chapter 2.5.1 --- Random Oracle Model --- p.19 / Chapter 2.5.2 --- Generic group model (GGM) --- p.20 / Chapter 3 --- Signature Scheme --- p.21 / Chapter 3.1 --- Introduction --- p.21 / Chapter 3.2 --- Security Notation for Digital Signature --- p.23 / Chapter 3.3 --- Security Proof for Digital Signature --- p.24 / Chapter 3.3.1 --- Random Oracle Model for Signature Scheme --- p.24 / Chapter 3.3.2 --- Adaptive Chosen Message Attack --- p.24 / Chapter 3.4 --- Schnorr Identification and Schnorr Signature --- p.25 / Chapter 3.4.1 --- Schnorr's ROS assumption --- p.26 / Chapter 3.5 --- Blind Signature --- p.27 / Chapter 4 --- Spontaneous Anonymous Group (SAG) Signature --- p.30 / Chapter 4.1 --- Introduction --- p.30 / Chapter 4.2 --- Background --- p.30 / Chapter 4.2.1 --- Group Signature --- p.30 / Chapter 4.2.2 --- Threshold Signature --- p.31 / Chapter 4.3 --- SAG signatures --- p.33 / Chapter 4.4 --- Formal Definitions and Constructions --- p.35 / Chapter 4.4.1 --- Ring-type construction --- p.36 / Chapter 4.4.2 --- CDS-type construction --- p.36 / Chapter 4.5 --- Discussion --- p.37 / Chapter 5 --- Blind Spontaneous Anonymous Signature --- p.39 / Chapter 5.1 --- Introduction --- p.39 / Chapter 5.2 --- Definition --- p.40 / Chapter 5.2.1 --- Security Model --- p.41 / Chapter 5.2.2 --- Definitions of security notions --- p.41 / Chapter 5.3 --- Constructing blind SAG signatures --- p.43 / Chapter 5.3.1 --- Blind SAG signature: CDS-type [1] --- p.43 / Chapter 5.3.2 --- "Blind SAG signature: ring-type [2, 3]" --- p.44 / Chapter 5.4 --- Security Analysis --- p.44 / Chapter 5.4.1 --- Multi-key parallel one-more unforgeability of blind signature --- p.45 / Chapter 5.4.2 --- Security of our blind SAG signatures --- p.47 / Chapter 5.5 --- Discussion --- p.49 / Chapter 6 --- Linkable Spontaneous Anonymous Group Signature --- p.51 / Chapter 6.1 --- introduction --- p.51 / Chapter 6.2 --- Related work --- p.51 / Chapter 6.3 --- Basic Building Blocks --- p.52 / Chapter 6.3.1 --- Proving the Knowledge of Several Discrete Logarithms --- p.53 / Chapter 6.3.2 --- Proving the Knowledge of d Out of n Equalities of Discrete Logarithms --- p.55 / Chapter 6.4 --- Security Model --- p.57 / Chapter 6.4.1 --- Syntax --- p.57 / Chapter 6.4.2 --- Notions of Security --- p.59 / Chapter 6.5 --- Our Construction --- p.63 / Chapter 6.5.1 --- An Linkable Threshold SAG Signature Scheme --- p.63 / Chapter 6.5.2 --- Security --- p.65 / Chapter 6.5.3 --- Discussions --- p.67 / Chapter 7 --- Conclusion --- p.70 / Bibliography --- p.72

Universiẗat, Diss., 2006--Saarbrücken.

No description available.

by Chan Hing Che. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (leaves 59-[61]). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Abstract Algebra --- p.8 / Chapter 2.1.1 --- Group --- p.9 / Chapter 2.1.2 --- Ring --- p.10 / Chapter 2.1.3 --- Field --- p.11 / Chapter 2.1.4 --- Useful Theorems in Number Theory --- p.12 / Chapter 2.2 --- Discrete Logarithm --- p.13 / Chapter 2.3 --- Solving Discrete Logarithm --- p.14 / Chapter 2.3.1 --- Exhaustive Search --- p.14 / Chapter 2.3.2 --- Baby Step Giant Step --- p.15 / Chapter 2.3.3 --- Pollard's rho --- p.16 / Chapter 2.3.4 --- Pohlig-Hellman --- p.18 / Chapter 2.3.5 --- Index Calculus --- p.23 / Chapter 3 --- Forging ElGamal Signature --- p.26 / Chapter 3.1 --- ElGamal Signature Scheme --- p.26 / Chapter 3.2 --- ElGamal signature without hash function --- p.29 / Chapter 3.3 --- Security of ElGamal signature scheme --- p.32 / Chapter 3.4 --- Bleichenbacher's Attack --- p.34 / Chapter 3.4.1 --- Constructing trapdoor --- p.36 / Chapter 3.5 --- Extension to Bleichenbacher's attack --- p.37 / Chapter 3.5.1 --- Attack on variation 3 --- p.38 / Chapter 3.5.2 --- Attack on variation 5 --- p.39 / Chapter 3.5.3 --- Attack on variation 6 --- p.39 / Chapter 3.6 --- Digital Signature Standard(DSS) --- p.40 / Chapter 4 --- Quadratic Field Sieve --- p.47 / Chapter 4.1 --- Quadratic Field --- p.47 / Chapter 4.1.1 --- Integers of Quadratic Field --- p.48 / Chapter 4.1.2 --- Primes in Quadratic Field --- p.49 / Chapter 4.2 --- Number Field Sieve --- p.50 / Chapter 4.3 --- Solving Sparse Linear Equations Over Finite Fields --- p.53 / Chapter 4.3.1 --- Lanczos and conjugate gradient methods --- p.53 / Chapter 4.3.2 --- Structured Gaussian Elimination --- p.54 / Chapter 4.3.3 --- Wiedemann Algorithm --- p.55 / Chapter 5 --- Conclusion --- p.57 / Bibliography --- p.59

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analog of the Digital Signature Algorithm (DSA) and a federal government approved digital signature method. In this thesis work, software optimization techniques were applied to speed up the ECDSA for a particular NTST curve over GF(p). The Montgomery multiplication is used extensively in the ECDSA. By taking advantage of the algorithmic properties of the Montgomery multiplication method, special structure of the curve parameters and also applying certain fundamental and specific software optimization techniques, we have achieved an overall 26% speed improvement. Further enhancements were made by implementing the Montgomery multiplication in the ARM assembly language that resulted in 44% speed improvement. The optimizations discussed in this thesis could easily be adapted to other curves with or without changes. / Graduation date: 2002