Document Number C004883
Copyright (C) 2009 CONNOTECH Experts-conseils inc.
Verbatim redistribution of the present document is authorized.
Also authorized are derivative works from the contents of document annexes A and B.
This document is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Specifications subject to change without notice.
Table of contents
Fixed an elementary security issue with the absence of length encoding for salt bits in the hash function input, see second paragraph in section "5.2 Signature Operation".
Added the annex "B. Software Utilities Design Notes".
Fixed the section "6. What's in a Name" which should have been updated with the salt legth encoding added with the previous document revision.
Changed some of the mathematical notation used in the section "5.2 Signature Operation", highlighted the potential for implementation optimization, added the reference [BERNSTEIN-TIGHT2003], and adjusted the formula for R.0.
Included a missing procedure element from the original Williams proposal, which made the verification procedure description inaccurate for half of signatures. Changes to sections "5.2 Signature Operation" (10th paragraph), "18.104.22.168 Verification Procedure with the Investigation Approach" (1st paragraph), and "22.214.171.124 Verification Procedure with the Assumption Approach" (three bulleted items).
Changed the Copyright authorization for annexes A and B.
Changed some trivial checks on S′ and T′ in the section "5.3.2 Signature Verification Procedure".
The public key cryptography digital signatures are well studied since the early publications by academics three decades ago. On the deployment front, many standardization efforts brought the digital signature techniques at the core of current computer networks. This document almost completely ignores such standards, and focuses on the theoretical foundations of the Rabin-Williams digital signature scheme; it merely describes a simple digital signature scheme including minimal interoperability provisions. While devoid of any advance to the art or science of applied cryptography, this document appears original in its formalization of a signature scheme details with this minimalistic approach centered on theoretical foundations.
Public key cryptography digital signatures were first introduced by Rivest, Shamir and Adleman in [RSA]. Soon afterward, Rabin modified the RSA signature scheme to introduce the public exponent 2 that came along with security proofs, see [RABIN]. In the same publication, Rabin suggested the use of message hashing for digital signatures. Williams proposed special a special form for digital signature key parameter that eases the computations, see [WILLIAMS-80]. An attempt to standardize digital signatures including RSA and Rabin-Williams is found in [ISO9796-2].
Basically, the present document records implementation guidelines for the digital signature scheme now known as Rabin-Williams with some hindsight available after almost three decades of theoretical refinements. We found inspiration in the papers by prof. Daniel Bernstein [BERNSTEIN-STOA] and [BERNSTEIN-TIGHT]. A difference with the work of Bernstein is that whenever it is an option, we prefer to describe what a signatory may do as part of the detailed signature operation specification instead of what he/she should do, e.g. we do not specify a size for public signature keys. In addition, our design orientation towards simplicity and straight application of theoretical refinements implied differences in the detailed provisions, including with respect to some details that changed with revisions of Bernstein publications.
The present work on a cryptographic signature design almost completely ignores digital signature standards. The exception is where a standard document refers to an element of the theoretical foundations and security proofs. The impact of standards on digital signatures is important, and the interested reader is referred to the reference [TS_102_176] that illustrates how far reaching standards might become, but also covers many digital signature implementation issues with an accessible presentation. The next section gives the design criteria, providing some background about our unusual position with respect to standards.
A goal of the present document is to allow a software developer to implement digital signature operations (basically signature key pair generation, signature generation, and signature checking) so that signature checking is as reliable as the theoretical foundations allow, leaving aside (or out of scope) any aspect that rests on compliance to system rules by other parties. The emphasis on theoretical support for the signature checking is the positive counterpart to the lack of attention to standards.
At the end of the specification drafting exercise, there remains a few provisions in the signature operation that are not direct and unequivocal consequences of theoretical foundations, and that are both important for interoperability with the signature verification and not left as signatory's options. So, we needed a name for them. The origin and meaning of the name scirpo is thus given in section "6. What's in a Name".
A couple of concluding introductory observations should assist the neutralization of preconceived ideas about digital signatures for the knowledgeable reader. Firstly, it is a very rational behavior for someone to abstain from digitally signing anything. The promoters of digital signatures forgot the basic lesson any child should receive as an early teenager: someone should only sign anything if a) there is a definite incentive and fair counterpart for the consequences of the signature operation, and b) at the time the signature is given, the signatory should feel free not to sign. It is thus not an accident that client-side digital signatures had virtually no market success with applications limited to granting access to computing resources.
Moreover, a security certificate is totally useless to a judge, even the most technology inclined one we could imagine. What a judge would seek is direct proof of ownership and continued control of the digital private signature key alleged to be the signatory's. Routine validation of digital signatures with security certificates is a mere automation feature for third party trust transitivity, and has nothing to do with non-repudiation. These observations about public key are out of scope for the present document but should bring the reader back to the genuine capabilities of public key cryptography.
Irrespective of these observations, the reader may wonder why the Rabin-Williams digital signature scheme has found little practical deployment in contrast to e.g. RSA, and consequently adhere to the general consensus that standardized RSA is the correct choice. The present document is not intended to change the reader's opinion, but merely to record what a simple Rabin-Williams implementation benefiting from theoretical foundations would look like. A comprehensive review of the security proofs for public key cryptography has been publiched by Koblitz and Menezes, [KOBLITZ-MENEZES].
As this document may be revised, its author sees three possible editorial directions.
Admittedly, these design criteria were not selected in abstraction of available cryptosystems. It just happens that the Rabin-Williams cryptosystem received improved theoretical support ever since its introduction, but it is seldom relied upon in the mainstream standardization activities. The design of an efficient and secure cryptographic hash function is notoriously difficult and critically dependent on independent reviews by academia, scientists, and graduate students throughout the world. In this respect, the NIST competition for an advanced hash standard is very significant. Otherwise, the focus on theoretical support reflected in the above definition of a digital signature is independent of preconceived solutions.
In the signature checking environment, the relevant one-way trapdoor function is defined by the alleged public modulus for the Rabin-Williams cryptosystem. That is, a large enough composite integer N=P×Q, where P and Q are primes satisfying P≡3 (mod 8) and Q≡7 (mod 8). With the expected secrecy protection applied to the factors P and Q, important characteristics of N may not be validated by direct computations on N. Nonetheless, modulus size and compositeness may be checked. The present document leaves out of scope the way the signature environment might learn about N, its association with any application-defined entity, and the secrecy protections applied to the factors P and Q.
In a variant of the digital signature scheme, the signature verification operation needs neither large integer division nor large integer modulo operation.
In addition, the signature checking environment should have a-priori knowledge of which cryptographic hash function(s) is(are) acceptable, and a trustworthy software implementation of it(them). In theory, the signature scheme is no stronger than the weakest acceptable cryptographic hash function, so it is a matter of defense against broken hash function attacks in signature checking environment to accept only hash functions that are deemed secure.
The signature checking environment should have a trustworthy knowledge of a mathematical constant with the same precision as the size of the largest expected composite integer N. Specifically, the bit pattern for the value log(2) (
0.693147180559945... in decimal,
0.D8E48EFEB83FE95D397CDC910CF4F65F20FC2C46... in hexadecimal) is used as fixed arbitrary data in the digital signature scheme in a place where the numerical value zero would create a security weakness. The intriguing Plouffe algorithm [PLOUFFE] for pi hexadecimal expansion is made from a more basic algorithm for constants that can be expressed mathematically in a given form. It happens that the most basic constant of this form is log(2). It is thus elegant to rely on the Plouffe algorithm for the trustworthy knowledge of the mathematical constant log(2). Obviously, other basis of trustworthy knowledge of the required bit pattern are available.
In the signature key pair generation environment, the legitimate signature scheme participant wishes to prevent any information leak about the private key (i.e. the prime factors P and Q). This includes a very critical requirement for a source of random secret binary data with a high resistance to analysis. Once the key pair is generated, any leftover clues about the required computation are threatening the privacy of the private key, notably swap files on a computer disk that can be investigated to recover internal data structures that are useful clues to an adversary.
There are various strategies for the generation of the two large random prime numbers that make up the Rabin-Williams digital signature key pair. Relevant issues include the extent to which number-theoretic properties should be verified and/or enforced, and whether the random prime numbers are selected so that no probability bias can be exploited by an adversary. The participant is relying on the key pair generation software supplier for these matters, at least to some extent with respect to their implementation (software auditing may provide some assurance).
The legitimate signature scheme participant wishes to keep the private key value indeed secret and the private key usage under strict authorization control. This is a basic requirement for a digital signature scheme to provide authentication assurance as expected. Safeguarding a secret in a computer system is notoriously difficult in the presence of powerful adversaries, so this aspect of digital signature operations deserves special attention.
In order to benefit from the Rabin-Williams theoretical foundations, the participant wishes to avoid the use of the private key for signing arbitrary data. This recommendation generally applies to any public key cryptography scheme; it is merely stressed by the security proofs that exist mainly for the Rabin-Williams scheme.
In practice, the participant wishes to avoid signing any message that is either not useful and meaningful, or not processed by a cryptographic hash function as specified in the detailed provision of the present signature scheme design. Like in the key pair generation environment, the participant is relying on the software supplier for these matters.
If the participant wishes to rely on a probabilistic digital signature scheme instead of a deterministic one, a need arises for a source of random secret binary data with a high resistance to analysis.
The Rabin-Williams signature scheme lacks a good reference specifications document. Much credit is due to prof. Daniel Bernstein for his continued dedication to this signature scheme, see his publications [BERNSTEIN-STOA] and [BERNSTEIN-TIGHT].
The reference [BBS] explores in depth the number theory applicable to the primitive operation of the form x2 mod N where N is the product of two distinct prime numbers each congruent to 3 modulo 4. Many diverse cryptosystems make use of this x2 mod N primitive, including the present author's [PEKE] for a symmetric secret key establishment protocol.
Just for the plain digital signature scheme, there are many minor variations and reformulations of the Rabin-Williams scheme, mainly variations in the handling of the 4:1 ambiguity intrinsic to the x2 mod N primitive ([SHIMADA], [HARN-KIESLER]). In a sense, Hugh C. Williams himself contributed to the reformulation trend: a summary of his famous cryptosystem found in [WILLIAMS-85] looks different from the original publication in [WILLIAMS-80].
Note that the present document does not attempt to provide a better specifications for the Rabin-Williams cryptosystem. Firstly, the cryptosystem includes a public key encryption scheme as well as a signature scheme, but the former is ignored in the present document. Also, our design criteria stay away from a standard drafting approach.
Simply select two prime numbers P, Q, where P≡3 (mod 8) and Q≡7 (mod 8) as the private key and N=P×Q as the public key. A legitimate signature scheme participant wishes the secret primes to be about the same size and large enough for to make impractical the factorization of their product N computationally. What is large enough may be influenced by prevailing opinions on the subject among entities which may validate signatures to be generated with the key pair. Beyond these elementary guidelines, the literature about the selection of RSA modulus applies to the Rabin-Williams modulus.
The signature operation starts with a standards-based hash operation applied to the signed message, optionally prefixed with random salt, giving a hash code value having a bit length h. The legitimate and voluntary signatory wishes to use a secure hash function defined with h at least 160 according to the prevailing opinions on the subject. The signature operation needs an unambiguous specifications for converting the hash code value into an integer H in the range 0≤H<2h. When the defining document for the standards-based hash function defines a large integer representation for the hash output value, this definition should prevail. When the defining document uses a sequence of CPU register values as a notation for the hash output, the big-endian convention should apply to the conversion. When the defining document uses more than one CPU register sizes for such notation, the big-endian convention should apply to the notation using the smallest CPU register size (this would disambiguate a defining document mandating the little-endian storage of 32 bit words into a byte sequence). The defining document for a standards-based hash function should be understood to exclude a separate digital signature specification that would mandate its own hash output conversion to a large integer.
The signature operation allows some salt bits to be prefixed to the message before applying the hash function. These salt bits, if any, are prepended to the message bits, and then an encoding of their count is prepended to the result. The encoding of salt bit count is a sequence made of an integral number of 8 bit bytes, with each but the last one having the most significant bit set (i.e. bit of weight 27). The count of salt bits is an unsigned binary integer made of the bits of weigths 26 to 20 from the first byte, followed by the bits of weigths 26 to 20 from the second byte, and so on up to the last byte. The encoded sequence shall be minimal to unambiguously encode the count of salt bits including a count of zero, i.e. the first byte value shall not be 27. The salt length encoding in the hash function input is needed to prevent a trivial signed message modification by moving bytes at the beginning of the signed message between the salt sequence and the message sequence.
A more theoretical concern motivates the message salting itself. A signatory wishes to avoid signature operational environments vulnerable to chosen ciphertext attacks and thus may use the salt option as a countermeasure opportunity. Typically, salt bits prepended to a message before hashing are obtained from a secret random source during the signature operation. They may also be derived from a secret hash function applied to the message to be signed. The actual method makes no difference at the signature verification time and is thus left as a local implementation issue. It is nonetheless an important aspect of the legitimate signature scheme participant security since it differentiates a probabilistic digital signature scheme (as originally intended by Rabin) from a deterministic one.
When salt bits are prepended to the message, they become part of the digital signature value. For this purpose, the salt bits are converted to an integer using the big-endian convention, and added to 2l, where l is the salt bit count, giving the salt bits representative integer σ. Hence, when no salt bits are selected, σ=1. Because it is a common practice and because the signature verification procedure below suggests that verification may fail with non octet-aligned input message and/or salt, the legitimate and voluntary signatory may insist that the bit length for both the signed message and salt be a multiple of 8.
For greater determinism, here is a description of the big-endian convention. When a string of bits need to be converted into an integer, the integer becomes the number having binary representation equal to the binary string, where the left-most bit of the string is considered as the most significant bit of the binary representation. Within a CPU register (either a byte or a larger computer word), the left-most bit is the most significant one. Within a sequence of CPU register values representing a string of bits, the left-most bit in the first value is the left-most bit in the string of bits. When an integer need to be converted to a string of w bits, the string of bits becomes the binary representation of the integer, with the left-most bit of the string corresponding to the most significant bit of the binary representation. If the resulting string of bits has less than w bits, then the string is left-padded with the appropriate number of zeroes to make it of length w.
Then, we use the notation n as the bit length of the largest arbitrary binary string input to modulo N arithmetic without reduction, that is n is such that 2n<N<2n+1. While the required condition that n≥h+5 is easily met in practical implementations, the theoretical foundations use the full domain hash notion which corresponds to the largest possible hash output size h.
We then form an integer value conveying H, a couple of number-theoretic knacks, and some adhoc redundancy, with a size up to n bits. This integer V is made of four parts with the equation V=R1+R0+16×H+12. A redundancy constant R is defined as the reversed binary expansion of log(2), i.e. bit of weight 2i in R is set to the bit of weigth 2-(i+1) in log(2). The log(2) fractional representation in hexadecimal notation begins with
0.D8E48EFEB83FE95D397CDC910CF4F65F20FC2C46..., thus the reversed log(2) constant ends with
...62343F04FA6F2F30893B3E9CBA97FC1D7F71271B. A longer sequence is given in the Annex "A. Fixed Constant Value". Then, R0 is the bit complement of the single bit of weight 2h+4 in R (and all other bits to zero), and R1 is the (possibly empty) sequence of bits of weight 2n-1 to 2h+5 (inclusive) in R (and all other bits to zero). In another formulation, R0=2h+4-((R-R mod 2h+4)) mod 2h+5), and R1=(R-R mod 2h+5) mod 2n. The condition that V≡12 (mod 16) is sufficient for to counter the number-theoretic threat of natural powers as explained in reference [GUILL_QUISQ]. When h and n-h are about the same magnitude (which is the case in practice), the non-zero high significant portion R1 avoids the instances of the x2 mod N primitive where no modulo reduction occurs. Because it is a fixed value (i.e. an instance of verifiable redundancy), R1 also prevents signature forgery attacks that depend on arbitrary bits at these locations, e.g. Annex C in [ISO9796-2]. No specific security benefit may be claimed for the R0 convention: the signature verification context is assumed to protect itself against the vulnerabilities of weak hash functions.
The integer V being the input to the number-theoretic computation in the Rabin-Williams scheme, the signature operation goes on with the computation of the the Jacobi symbol (V|N)=(V|P)×(V|Q). While in the public key encryption scheme, the Jacobi symbol computation (V|N) is not as readily optimized as other elementary operations in public key cryptography, this concern is moot in the digital signature scheme because the private factors P and Q are known. Thus, the computation of (V|P)×(V|Q) goes as follows: compute
(V|P)=(V mod P)(P-1)/2 mod P
, which gives either 1 or P-1; turn any P-1 result into a small signed integer -1; compute
(V|Q)=(V mod Q)(Q-1)/2 mod Q
, which gives either 1 or Q-1; turn any Q-1 result into a small signed integer -1; finally return (V|N)=(V|P)×(V|Q). Then we define a quantity J as J=1 if (V|N)=1 and J=2 otherwise. Finally, we let C=V/J. The basic contribution of Hugh C. Williams (reference [WILLIAMS-80]) finds its application here: provided the public key N is generated as indicated above and since V is a multiple of 4, the Jacobi symbol (C|N) is 1 and C is a quadratic residue modulo N.
Note that some variants of the Rabin-Williams cryptosystem, and the present one in one of its optional mode, are making explicitly part of the signature the Jacobi symbol information conveyed in J. In addition, some variants of the Rabin-Williams cryptosystem, but not the present one, are specifying separate processing for H even or odd and making the parity of H an explicitly part of the signature. With respect to the essence of the Rabin-Williams cryptosystem, all these variants appear equivalent.
The signature operation then proceeds with finding integers s such that s2≡C (mod N), and 0<s<N, but the Rabin-Williams theory teaches that in half of the cases, solutions will be found for s2≡N-C (mod N) instead. For the signature operation, this is without consequence because the disambiguation is postponed to the signature verification. Irrespective of which equation happens to be solved, there are four solutions, say sA, sB, sC, and sD, with the property that sA+sD=N and sB+sC=N. A legitimate signature scheme participant wishes to always reveal a solution from a single pair whenever a given V is submitted twice or more in the signature operation for some N. Otherwise, someone other than the legitimate participant may quickly find the secret factors P and Q from N and e.g. sD and sB.
To find the four solutions sA, sB, sC, and sD from C, P, and Q, the procedure uses the Chinese remainder theorem and properties of quadratic residues, and goes as follows. To make computations more efficient, we may pre-compute integers a and b such that a×P+b×Q=1 (using the generalized Euclid algorithm).
Given an integer C, recovery starts with the following computations:
μ = (C mod P)(P+1)/4 mod P
ν = (C mod Q)(Q+1)/4 mod Q
The initiator may then compute the four possible values for x:
sA = (b×Q×μ + a×P×ν) mod N
sB = (b×Q×(P-μ) + a×P×ν) mod N
sC = (b×Q×μ + a×P×(Q-ν)) mod N
sD = (b×Q×(P-μ) + a×P×(Q-ν)) mod N
Various standards and other publications about the Rabin-Williams signature scheme make recommendations about which of sA, sB, sC, and sD is to be included in a digital signature value. The two prevailing strategies are "always sA" or "the smallest of sA and sD". While a random selection would be insecure when a given C is submitted twice to the signature operation for some N, there may by a rather theoretic security advantage in an arbitrary but deterministic selection, e.g. based on a two bit secret hash function applied to V. In any event, we denote the selection as S.
Without any of the optional steps to be explained shortly, the signature operation output is made of the two integers S and σ.
The above computations for the Jacobi symbol and the signature solutions are closely related and have much numerical processing in common. This leads to an implementation optimization opportunity, the details of which are omitted. This has been reported in section 6 in [BERNSTEIN-STOA] but the comprehensive explanation seems to be provided as algorithm 3.1 and theorem 3.2 in a draft academic publication, i.e. [BERNSTEIN-TIGHT2003].
The final optional steps in the signature operation require no knowledge of the private key, and merely provide a transfer of processing load (or complexity) from the verification phase to the signature phase, with the additional burden of a larger signature size.
The first optional element is to include in the signature operation output the integer T=⌊S2/N⌋.
The second optional element is to include in the signature operation output the integer J. This second optional element is useful (i.e. offers a potential efficiency gain at the signature verification phase) only when the first optional element is also present.
In practice, an application use of digital signature verification is a much more encompassing activity than just applied number theory. The present note aims at avoiding the misappropriation of theoretical findings as evidence that an application is sound. It also describes the (limited) scope of signature verification as specified here. An informal decision tree is presented as a model of what can happen to a single transaction in an application that may rely on digital signatures. This decision tree applies when multiple signatories are relied upon, such as when validating a chain of security certificates and and end-entity signature.
The present document specifies at an abstract level what a digital signature verification software may do to recognize valid signatures (decision tree entry 3.2) and, to the extent possible, provide an application-level signal that decision tree entry 2.2.1 or 2.3 has been encountered instead of an unspecified failure.
The signature verification procedure may start when provided with three, four, or five positive integer values, plus the allegedly signed message in the form of a bit sequence. The five integers are the alleged public key N′, the mandatory signature components S′ and σ′, the optional signature element T′, and the optional signature element J′ (we use alternate mathematical symbols to highlight the absence of known properties for these inputs despite their expected correspondence with symbols used in the signature operation). No further data format specifications need be given for the purpose of the present document. In the same spirit, the integer input σ′ representative of the message salt may take the form of a bit sequence like the message.
Likewise, the verification procedure outcome is lousely defined. Any element of the procedure may provide information to the application in which it is hosted, but the intended semantic is to return a result code with four possible values:
Moreover, in at least in one aspect, the signature verification semantic is somehow left unspecified as an application issue: an otherwise verified signature may be rejected by an application because the size of the public signature key is considered too small, but this is left unspecified in the verification procedure itself.
Any test failure involving the optional input T′ or J′ may trigger a fallback of the verification procedure to its basic mode if the verification software supports it.
The verification procedure may stop and report an unsupported procedure element if either the salt size or the message size is not a multiple of 8 bits. In the case of the salt represented by the integer σ′, the size is a multiple of 8 bits if and only if 2v≤σ′<2v+1 with v exactly divisible by 8.
The verification procedure should stop and report an unsupported procedure element if either N′ is less than 2128, or S′ or T′ is significantly shorter than N′, e.g. less than N′×2-48. The first check is specified as an indication that large precision integers are expected as inputs to the verification procedure, and not as a security level threshold.
A few other trivial checks, which detect obviously invalid public signature inputs, are that N′≡5 (mod 8), that S′<N′, that σ′>0, that T′<N′, and that J′ be either 1 or 2. The verification procedure should stop and report an unsupported procedure element if any of these tests fail.
After these preliminary checks, the verification procedure may proceed with either the investigation approach, or the assumption approach, where the difference lies in the level of presumption about the signatory procedures. While the investigation approach presumes less, the assumption approach presumes that the signatory applied the signature procedure specified in the sections "126.96.36.199 Verification Procedure with the Investigation Approach" and "188.8.131.52 Verification Procedure with the Assumption Approach". While the end-result is identical with either approaches, the investigation approach might provide hints (diagnostic or troubleshooting data) about alternate signature procedure that could have been followed by the signatory. The assumption approach has more potential efficiency shortcuts, and looks better suited to routine signature verification applications.
With the investigation approach, the signature verification inputs are suspect of non-compliance to the greatest extent. As a consequence, the optional inputs T′ and J′ should be ignored until the signature has been verified without them. A later check on these optional inputs would be useful only to determine that these values do not hold information unrelated to the digital signature encoding.
The investigation approach may be part of a broader data investigation activity. It could for instance start after N′ has been qualified as a large composite integer with no small factors. Then a failure of the test N′≡5 (mod 8) could indicate that a digital signature procedure other than Rabin-Williams is present.
With either the investigation or the assumption approach, the verification procedure has a-priori knowledge of a set of candidate secure hash specifications, each with a defined output bit count. In the assumption approach, this set is typically a single element since a hash function convention would be part of the presumed signature generation context.
Then, the verification procedure can proceed with the large number arithmetic operation at its core, that is to compute S′2 mod N′. If this result is an even number, let C′=S′2 mod N′, otherwise the odd result turns into C′=N′-S′2 mod N′.
Then, the low order four bits of C′, i.e. C′ mod 16, are inspected. Any value other than 6, 12, and 14 should cause the procedure to stop and report a breach of formal cryptosystem rules. Then the procedure assigns V′=C′ for the value 12, and V′=C′×2 for either the value 6 or 14. Upon failure of this test, a broader investigation context might consider alternate Rabin-Williams detailed procedures for message encoding, but this is outside the scope of the present document.
It may be tempting to check the Jacobi symbol for V′ in order to detect a breach of cryptosystem rules (it should be 1 for the above 12, and -1 otherwise). However, an enemy attempting to have a signature validated with an arbitrary public key can easily create one in compliance with the cryptosystem rules, so the Jacobi computation appears to provide marginal investigative value.
The signature verification then proceeds with the recognition of a known bit pattern in the binary representation of V′. The present specifications uses the reversed binary representation of the fractional part of log(2) as a known bit pattern. In a valid signature, the binary correspondence must be verified in every bit position, if any, from weights 2n′-1 to 2h′+5 inclusive, with n′≥h′+5, where n′ is such that 2n′<N′<2n′+1, and at least one of the candidate hash functions has h′ as its output bit count. Furthermore, in the binary representation of V′, a zero must appear at the bit position with weight 2n′ and the bit position with weight 2h′+4 must hold the complement of the same bit position in the known bit pattern. If any of these conditions fail, the signature verification should stop and report a breach of formal cryptosystem rules. Otherwise, the signature verification proceeds with the remaining sub-range in the binary representation of V′, i.e. from weights 2h′+3 to 24 inclusive; this remaining subrange is extracted as the integer H′=⌊V′/16⌋ mod 2h′.
At this point, the signature verification is about to consider the salt bits. When these are encoded in the input integer σ′, the salt bit count is given by the integer v such that 2v≤σ′<2v+1, and the integer representation for the salt bits is σ′-2v. These v salt bits are converted from this integer representation to a bit string of length v using the big-endian convention.
Then, each candidate hash function with an output bit count h′ is tried with the salt bits (and salt bit count) prepended to the allegedly signed message, the result is converted from a bit string to an integer H″, and the integer H″ is compared with H′ (notation H″≟H′). Any equality should trigger the signature verification to conclude with a signature verified indication. If no such equality holds, the signature verification concludes reporting a breach of formal cryptosystem rules.
With the assumption approach to signature verification, the procedure elements are organized in part as a replay of signature generation procedure elements, up to the computation of integer V or C, but using the allegedly signed message prepended with salt bits (and salt bit count) found in σ′, up to the respective computation of integer V″ or C″. This first part amounts to verification by repetition of detailed procedures. For the second part, the repetition of procedures in the verification environment is prevented by the absence of the private key data (factorization of N′). The main inputs to the second part are N′ and S′. For this second part, there are three variants based on how many of the two optional signature input elements (T′ and J′) are present and used.
In the first part, a salt (σ′) and allegedly signed message transform is applied with each candidate hash functions until one is found to verify the signature (this transform also needs n′ for the bit size of N′). This transform is identical to the one specified in section "5.2 Signature Operation" up to the integer V, and we use notation V″ in the context of signature verification for a single hash function. In the third variant below, the first part is extended to the computation of integer C″, using the explicit alleged Jacobi symbol indication J′.
The second part of the signature verification procedure using the assumption approach has the following three variants.
The name scirpo is a Latin word for I tie or I plait. It intentionally recalls the great bulrush, a freshwater aquatic plant by the scientific name scirpus lacustris (Linn.). This plant sturdiness comes from its rhizomes (recalling the Rabin-Williams theoretical foundations); its variations has been renamed by a few botanists; its distribution covers temperate areas in every continents; and its usefulness in textile craftsmanship is easily overlooked.
The name scirpo refers only to the few provisions in the signature operation that are not direct and unequivocal consequences of theoretical foundations, and that are both important for interoperability with the signature verification and not left as signatory's options. This includes essentially:
Many aspects of a digital signature scheme are left out of this definition. We see three avenues for managing this open-ended set of implementation options. In the unusual but interesting case where one signs a message sent to an enemy or a party with whom it is impractical to agree on a signature convention, the signature strategy is to self-assert the control of the private signature key and the authenticity of various messages sent over time. In this avenue, every option should be decided on the safe side and the reliance on the scirpo conventions and a specific hash function should be mentioned in a legible way within the message. The other avenue is a closed application encompassing both signature generation and verification, where the designer may determine the options derived from the verification perspective (mainly signature strength provisions), then the additional options that protects the signatory from signature forgery (e.g. elements of procedure for the selection of signature key pair), and lastly the other interoperability provisions.
The third avenue for handling our open ended definition of a digital signature is interoperability-driven applications. For these, the benefits of theoretical foundations associated with the Rabin-Williams signature scheme are currently not enjoyed: different standardized signature schemes have either a strong installed base advantage, i.e. RSA as in [RFC4055], or a strong institutional backing, i.e. ECDSA as in [FIPS186-3]. In this perspective, the present document is seldom more than a reminder of arguments put forward by Bernstein ([BERNSTEIN-TIGHT], [BERNSTEIN-STOA]) and echoed in [KOBLITZ-MENEZES].
Here is the least significant 16K bits, in hexadecimal notation, for the constant made as the reversed fractional binary expansion for log(2).
8F03AC20.0F29C9DD.9A802BF7.E92C4B78.7E9E4E43.CA2EE316.005BDB67.19AA2ED8 B47EF7DB.EC4EFBD4.BC47B0EA.76304866.5CCC3936.26F15DEF.9CCE2023.3C48E099 01D0C0CF.17B8D450.E34D09D9.DB83F911.1378D2FA.9CE2EEC8.77973B66.BB2530E8 027A5BD3.5F3E3C21.9E99122B.78D79928.31EF622F.A7BCFEA7.46D14084.75EE5CF6 8C4C93F5.26B0ADDB.49DE1A1D.59C4BA99.7BE803F7.B2B75204.C41F90BC.DEEF1D3B AA5B5430.AFFEBF75.18327599.8D399D7E.9F70D6E4.CB8FBD6B.B6BAD8E7.D5D4A44A 57C64EF4.1E81023F.76436565.FF742239.0657ADD3.DA37F9B2.F0AB2EBB.04642AD6 AE80CFEF.DC4CCC49.17CF7784.D176F343.9EC4B535.58B1B706.D15FD7EC.F082DF34 9A7B09DE.653EDAFE.35C599CE.DBB022AF.316AA27B.5ADB60D7.69DF0D88.698611EE 838A49EC.686E28B0.5910E899.A4060D30.FFB411CC.2DA4373A.20D7138F.C139FA59 0BB707FA.41D3F5DE.B3ACA058.34409CEE.906F90EB.4874209A.7ACD054C.F7509711 4C7A34CC.F157A02D.07097E0D.E67F302A.752E516D.B0110146.FDE1AA07.A4DCFF75 1725EF2E.E867D4AF.CA5E9926.1A54F2B1.CE8CDAF9.2B6589BC.B2DB3E10.6F1413A6 72E555A8.A126FA4B.5239E140.BDCD8295.87432210.13B2D810.FB7835D1.CAD7EAFA BB24A431.EC38755A.946A6AD0.216C8AB2.85D6FCC3.F02FA837.6770761F.80995A85 1FF98629.76BDF8EB.2229130F.938501D6.73DE5BAC.6F77B086.A1676200.AB7054AF 6C4BDFE5.B433C7C3.E94E627E.A64CD285.DBF2CEC2.51B07589.2C51D3D5.172E54C9 1D7BDA74.44DB725A.9A5F373A.09E748C7.FF039374.6CF18F30.B1822470.A3407A02 2D505F5B.B1CBC414.EE5AEDA8.562DE6A7.AD24347A.183630DF.78B88AF4.83EDEEA8 604BEA71.2685F7E9.D3AEBFE7.D99EA66D.3525BC84.9B53EC3C.601C290A.9C99C4A1 ED35B423.788F967A.1B7B1D77.121363C0.9976EE21.1E26934C.BC491C17.E0784964 5950A31D.DD6F5855.E3F1DED6.131055C6.D207FE4C.81DBBD59.1815F29C.0E5A8622 E69692CD.F6E37C2E.B54C90A4.6FFA109C.55F7409D.747E3357.2C4BCCEB.9AD52BD9 CF41FF19.22382A51.186E6C7D.3224861C.FF7BD1C9.76BE80E3.E7600773.D5C628DD BCBC9380.C1E55288.F07F422F.6C246718.749B8DFF.6B0EC4F7.4225D998.06B5EEA9 AC8F8822.E2CFF1FD.7E8CB33C.DF632EE7.7EB3BEA5.6B6E6110.AD2DBE87.D8649075 E78F7471.8BE3A06F.9E5B0CC8.769DF1FE.E8DB34FD.8087B8A5.70B77911.2E60B143 E4303605.8DC166B2.F424DDFD.533716DD.09067311.820ABB7C.17D3091E.9B1E7F6D 339D408F.A71DC7C7.8F57E5FA.1B009A72.51E0E89E.0EA2B10B.644C0F37.81AFB348 DBBFB2A7.768322B5.50A8686F.C1068AF0.7A637772.C9B53439.07E1DF26.D30266A5 EA1FBFA1.198AE61B.1B9BF709.6560FC77.35277D7D.1073E5CA.04DE5C5D.98D97AEF 89624B9E.BE76E441.F9658155.B09CC179.0BE7657F.CE1D8B4A.31C6BDD7.04CA9BBC 299A6631.C6CE175D.F8382C43.1EC0A534.CF67B3CC.C98EAA2D.3876A011.F26E49EE 6B3C3DCC.65868FAB.DE681413.8E210889.5927B78C.3BE688A8.488EC9AA.8C91203E 79767F2E.6DD228D1.D41F99CF.8E3EB258.03CCFE41.BD9319A5.E956988D.4038F743 BAC95C26.928A2104.26070715.0EAE95FD.97515441.4BAFD21B.49E26533.4324CB08 BFA7FE17.8506D6FA.DAAE7B37.A2B653A1.A0225913.CA69019F.9F63001D.F062F59C AC0042A8.9AEEEE9F.AC8D8CA8.9A580CD6.6B99DF75.02928086.B620A4A1.5A41F426 7E813585.1C5B5E37.BAAE10FF.0B36921C.5968616A.978255B2.18654F98.75049DF8 725381B4.A2D98D2F.2FBDF6FE.58F1ADB1.4FED3A9B.24BF4AA1.1073505A.AD1ECC6D 8B439487.859B41CA.96016420.2C8E5B21.45185665.6F190D3A.3F1571B3.50FA261D ADE4969B.4E235648.CC7037D9.4EFD977B.012B2124.CD34A8DA.2FE27AAF.C8A15EF6 A8E0A2E4.55685D88.2932BD3B.CC5BDC02.BB453AE6.79DC0F41.A88A0F54.4F4FB174 8DCF4220.22B320F0.9DBB5513.0958711F.CDF5CCAF.3753EC33.397FF2E0.2306C451 387B1F46.F3CEAD35.E105182F.6139A4BD.949F9C65.129CE2EB.C1430F49.D85F8AC0 00A4782D.7D30B455.C00E7945.FD57C0BF.60D24ACE.0580E6EE.F2CE22FE.A8B5F463 F9C36B87.EC93A798.834832E1.6133BA25.C06C4C6A.36A1B260.DDE07F8E.F9448AE3 C15CAF62.514A5246.0E48859F.D7675E5C.AF32E0A8.D13B1B0C.D0DB94A3.0BA6BD58 8DDAAD8C.FA4BE571.E473298A.3FFFA70F.E198AED0.526286F8.D93383C9.1F27BCEC EA54F9CA.BEC7F6F5.0C51167E.690274C6.24D9DBBF.B81DC279.427C76DB.BB111BA0 9B832C0A.DF628374.DBEAA42D.D6961C16.3E5D3142.92C0E651.7847E4CD.06448159 A646E109.8562267D.8593737D.2EC0F2FE.C7029E4C.C16B5CA2.50D7ABEB.2AB93375 C0A19380.994E0600.20305FA6.91363126.9F2DB0D3.5D821C50.9B688EEC.02B20E63 2F949D3F.AF61BBB0.9012499C.DE381224.5C3D66C8.8B2229E5.FC3AC1B6.44DFFA16 289B8359.F1C5A862.5570FCBF.7715F6D8.9FE4A822.1D39271A.E8CDC137.45520A44 B988FA03.3D6E4D69.438969F8.6C6B0755.EE372EA1.591A8957.D358563B.3BD261D4 B81C4605.815B05F5.B13BD2B1.D537F870.1BC606C6.BDC313EA.D9B71E1B.9715D559 C2D05371.45A084C0.3AA7EFC5.106BD470.28E841E5.A8F7C9A6.733A4653.33B96652 D5906D1D.B0E1A1C4.C4153939.56E4CCCC.33DC974B.237E349C.5E0998BD.57706471 693B0041.ED32E2D7.51AFE1CF.D6D965EE.2A155EF8.8F03D016.09BFB5BF.11AC4F70 6C5DF3F0.5C79D2AD.2A3E02F2.781AF556.84230383.DB6AFD5F.AC8456D9.1B78EC27 B47F7567.CE0AF652.B306631B.3CB9AE9B.E783C713.11ADBCA1.5C8EA422.61AC69E3 528B9611.92B37572.4412831C.53EAE2DE.01B1AFA4.BF255955.89CABED6.02678B7E B2AFAAB8.B571D0A8.D26B8927.62343F04.FA6F2F30.893B3E9C.BA97FC1D.7F71271B
This document annex gives design notes for software utilities implementing and demonstrating the Scirpo Rabin-Williams digital signature scheme minimal specification. These utilities are not intended as a reference implementation because the software runtime environment characteristics that would be safe is neither expressible with a conventional programming language nor readily available in typical computing devices. Instead, this annex contains design notes that are one step closer to an implementation, in some unspecified environment, than the main body of this document.
In this annex, the description of software utilities sometimes refers to mathematical notation introduced in the document main body. The relevant document section is "5.2 Signature Operation".
There are three required utilities, respectively
scirpo_keygen for signature key pair generation,
scirpo_sign for signature generation, and
scirpo_verify for signature verification. There are three data objects, respectively for a Rabin-Williams private key (two secret prime factors), a Rabin-Williams public key (the modulus being the product of the two secret prime factors), and a Scirpo digital signature. There are variations in the contents of a signature object, including ones that embed the public key in the signature. The following elements appear in a data sequence encoding a Scirpo signature: an optional modulus, a signature solution value, a salt field, an optional T value, and an optional J value (allowed only if T is also present). The latter two optional values are not relied upon by the signature verification utility since they merely provide performance gain opportunities which are relevant to production environments.
It is a goal of the software utilities design to support the variants in the Scirpo signature object as implied by the main body of this document, and to facilitate the use of object data representations in ASN.1 BER encoding (command line keyword
asn1), ASCII decimal (command line keyword
dec), and ASCII hexadecimal (command line keyword
hex). For this goal, the signature and verification utilities may be used for the sole purpose of data object transformations (for sake of unicity in a utility function, parameter combinations that trigger input object transformations disable the normal operation expected from the utility). It is worth stressing that the signature data object representation transform that computes and inserts the Jacobi symbol is present in the signature verification utility as a design choice but would be absent from production software: the Jacobi symbol computation is as straightforward as explained in the main body of this document when the secret prime factors are available, and not needed when the prime factors are unknown.
In the case of ASCII representation, the data objects encoding is either comma separated integers on a single line, or one line per integer with a label prefix such as
Salt= (command line keywords
hex-labels). When no labels are present, some disambiguation may be attempted from the fact that the Scirpo salt value is usually of a smaller magniture than other signature elements. Moreover, the software utilities are limited to byte-aligned data for the signed data and the salt field. With ASN.1 encoding, the salt field must be encoded in an ASN.1 data value of type OCTET STRING or BIT STRING (the rest of the ASN.1 syntax for the enclosing Scirpo signature is irrelevant as long as the data values are in the sequence indicated above).
More basically, the signature verification is an investigation of some meta-data alledgedly associated with a specific message, that results in either No valid digital signature found or Found a numerically valid digital signature with public key <literal modulus value> (some additional verbosity, e.g. an indication of the hash function, may be provided). The cryptography theory supports no further conclusion, i.e. it excludes anything inferred from additional semantic of a digital signature, and any assumption about either the computing environment in which the signature was generated (besides the fact that the factorization of the Rabin-Williams modulus was known) or the behavior of an entity in possession of this computing environment. The interoperability standard compliance of the meta-data in which the digital signature was found is likewise irrelevant to the signature semantic. It is thus a valid design for the signature verification utility to investigate unspecified data for the presence of a Scirpo signature for some input message, in any format, e.g. as a sub-tree in an ASN.1 parsed message tree or as an ASCII sequence within an utf-8 Unicode file. More than a single digital signature may be found in the meta-data.
Signature context signalling is out of scope for the software utilities design. This refers mainly to the usage context of a signature key pair, including any signatory entity identification, a hash function that a signatory would be deemed to use, and a signature validity period. The hash algorithm indications are given as command line arguments to the signature utility (a single hash algorithm) and the verification utility (one or more hash algorithms).
As a design choice, the software utilities that use a secret random source (i.e. key pair generation and signature whenever the salt size is greater than zero) do not provide a deterministic mode of operation in which a pseudo-random algorithm might be explicitly seeded. This restricts the software intrinsic value as a reference implementation and makes software validation somewhat more difficult, but is more typical of actual operational use of a cryptographic software or system.
scirpo_keygen utility is for signature key pair generation, and has the following synopsis:
scirpo_keygen [|--modulus-size <n>] [|--entropy <rng-option>] [|--private-key <file>] [|--format [asn1|dec|hex|dec-labels|hex-labels]] [|--encryption <passphrase-option>] [|--public-key <file> [|--format [asn1|dec|hex|dec-labels|hex-labels]]] [|--verbose <debug-level>] [|--help] [|--warranty]
The signature key generation utility is driven by the following core command line arguments:
The utility output specification is driven by a few more command line arguments:
Finally, three general-purpose command line arguments are recognized:
scirpo_sign utility is for signature generation, and has the following synopsys:
scirpo_sign --private-key <file> [|--format [asn1|dec|hex|dec-labels|hex-labels]] [|--encryption <passphrase-option>] [[|--input <file>] [|--hash [sha1|sha224|sha256]] [|--salt-size <n>] [|--root-select [quad|sa|abs-quad|sb|sc|sd]] [|--signature <file>] [|--format [asn1|dec|hex|dec-labels|hex-labels]] [|--embed-public-key|--no-embed-public-key] [|--t-in-signature [|--j-in-signature]] |--out-private-key <file> [|--format [asn1|dec|hex|dec-labels|hex-labels]] [|--encryption <passphrase-option>] |--out-public-key <file> [|--format [asn1|dec|hex|dec-labels|hex-labels]]] [|--entropy <rng-option>] [|--verbose <debug-level>] [|--help] [|--warranty]
The signature generation utility uses the decrypted contents of a private signature key file. This is specified with a few command line arguments:
In its normal operating mode, the signature generation utility operates on an input data file, to be signed, with a few command line arguments that govern the signature operation characteristics:
quadis a synonym for
saand corresponds to the strategy "always sA". The argument
abs_quadcorresponds to the strategy "the smallest of sA and sD". This command line argument finds its limited justification in a complete exposition of Rabin-Williams properties through the command line, and the default value, namely
quadshould be preferred for keeping out of the number-theoretic minefield. Indeed, the following security warning applies: if two signatures are given for the same message and same salt bits (e.g. with a salt bit length of zero), respectively with one of
sdand one of
sc, then the signature key pair is broken through easy recovery of the secret prime numbers (one of the prime factors is found by adding the two signature solutions and computing the greatest common divisor of the sum and the composite modulus).
Beyond the above substantive signature operation options, there are a few command line arguments that drive the signature data representation details:
In one of its two special modes, the signature generation utility merely copies the private key information, allowing data representation changes and/or encryption option or key change. This is driven by the occurrence of the first command line argument below:
In the second of its two special modes, the signature generation utility merely creates a public key representation based on the private key information, allowing data representation changes for the public signature key. This is driven by the occurrence of the first command line argument below:
Finally, four general-purpose command line arguments are recognized:
scirpo_verify utility is for signature verification. This operation has three main variants, respectively for the verification of a single isolated sigature, the inspection of meta-data for the detection of one or more valid Scirpo signatures, and a signature copy operation (from a single isolated signature) for data representation changes. Flexibility also lies in the way the verification utility learns about possible public signature public keys: through command line arguments, embedded in the signature data representation, or both. The verification output is one text line for each detected and validated signature, with argument-driven data fields on each line. The verification utility has the following synopsys:
scirpo_verify [--signature <file> [|--format [asn1|dec|hex|dec-labels|hex-labels]] |--meta-data <file>] [|--embedded-public-keys |[--public-key <file> [|--format [asn1|dec|hex|dec-labels|hex-labels]]]... [|--other-public-keys|--no-other-public-keys]] [[|--input <file>] [|[--hash [sha1|sha224|sha256]]...] [|--modulus-size <n>] [|--salt-size <n>] [|--inspect-public-key|--no-inspect-public-key] [|--output <file>] [|--output-format [1|m|k|h|s|c|p|l|f]...] |--out-signature <file> [|--format [asn1|dec|hex|dec-labels|hex-labels]] [|--embed-public-key|--no-embed-public-key] [|--t-in-signature [|--j-in-signature]]] [|--verbose <debug-level>] [|--help] [|--warranty]
The digital signatures to be verified are either an isolated one present in an input file or possibly many to be identified among unspecified meta-data. Correspondingly, there are command-line arguments:
The verification utility must be told about the public signature keys it should handle.
--no-other-public-keysoption, the verified signatures may embed a public key also sepcified in one of the explicit public key files.
In its normal mode of operation, the verification utility applies to a specific data file, and according to some user-supplied verification criteria.
In its normal mode of operation, the verification utility output some signals that would be of interest to an application software. These signals are nowhere in the error reporting verbosity level scale (i.e. emergency, alert, critical, error, warning, notice, info, debug). The utility uses a separate output stream for the signature verification signals.
1is the fixed text signed,
mis the public key modulus value in hexadecimal notation,
kis the public key modulus size as a decimal bit count,
his an indication for the hash function that verified the signature,
sis the salt size as a decimal bit count,
cis the fixed text Scirpo intended for future expansion where the utility would recognize signatures complying to other schemes,
pis the position (byte offset) of signature data within the meta-data input file,
lis the length (byte count) of signature data within the meta-data input file, and
fis the format (same keywords as for the option
--format) of signature data within the meta-data input file. The default value is
mand allows the recovery of a public key file from a valid digital signature.
In its special mode, the signature verification utility merely copies the digital signature, allowing data representation changes. This is driven by the occurrence of the first command line argument below:
Finally, three general-purpose command line arguments are recognized: