Scirpo, a Basic Rabin-Williams Digital Signature Specification

Thierry Moreau

Document Number C004883

2009/09/02

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

1. Abstract

2. Introduction

2.1 Editorial Directions

3. Design Goals

4. Digital Signature Usage Environment Characteristics

4.1 Signature Checking Environment

4.2 Signature Key Pair Generation Environment

4.3 Signature Generation Environment

5. Procedure Specifications

5.1 Signature Key Pair Generation

5.2 Signature Operation

5.3 Signature Verification

5.3.1 A Note About Application Use of Digital Signature Verification

5.3.2 Signature Verification Procedure

5.3.2.1 Verification Procedure with the Investigation Approach

5.3.2.2 Verification Procedure with the Assumption Approach

6. What's in a Name

7. References

A. Fixed Constant Value

B. Software Utilities Design Notes

B.1 Overview and Principles

B.2 Signature Key Pair Generation

B.3 Signature Generation

B.4 Signature Verification

Document Revision History

C-Number

Date

Explanation

C004883

2009/09/02

Current version

C004861

2009/07/27

Initial release

C004879

2009/08/19

Added the section "2.1 Editorial Directions" and the reference [ISO10118-4].

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".

C004883

2009/09/02

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), "5.3.2.1 Verification Procedure with the Investigation Approach" (1st paragraph), and "5.3.2.2 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".

1. Abstract

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.

2. Introduction

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].

2.1 Editorial Directions

As this document may be revised, its author sees three possible editorial directions.

3. Design Goals

Definition for Digital Signature
The design criteria are dependent on a definition for digital signature.
A digital signature is defined as a data element associated with an allegedly signed message, and that can be inspected to determine whether it could have been computed only with the trapdoor information of a given one-way trapdoor function; absent such determination, the digital signture is meaningless.
This definition avoids the notion of an entity that signs. Indeed there is no theoretical modeling for a signature apparatus or its controlling entity. Moreover, the definition stresses the finality of a digital signature: signature checking.
Theoretical Support
Theoretical foundation is important. It should be supported by the work of reputable cryptographers published in reasonably accessible presentation. Older theoretical contributions should be prioritized.
No Emphasis on Standard Compliance
Standards may be ignored. They should be avoided when they tweak any direct input to a public key cryptography primitive, like the ASN.1 object identifiers in the PKCS#1 standard.
Exception with Cryptographic Hash Function
As an exception to the standard avoidance design criteria, a cryptographic hash function needs to be standards-based. This precludes the MASH algorithm despite its formal publication as an ISO/IEC standard: it is not a deployed standard.
Design Simplicity
The digital signature scheme should stress conceptual elegance and implementation simplicity more than computation, memory and/or bandwidth efficiency.

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.

4. Digital Signature Usage Environment Characteristics

4.1 Signature Checking Environment

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.

4.2 Signature Key Pair Generation Environment

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).

4.3 Signature Generation Environment

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.

5. Procedure Specifications

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.

5.1 Signature Key Pair Generation

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.

5.2 Signature Operation

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.

5.3 Signature Verification

5.3.1 A Note About Application Use of Digital Signature Verification

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.

1. Insecure Transaction
Most applications existed before digital signature verification has been added, and/or are allowed to process insecure transactions under certain conditions. It is thus a first line of attack to bypass the digital signature verification mechanism, but any such doubtful transaction may remain undetected among the legitimate but insecure ones.
2. Signature Verification Failure Observed
In this part of the decision tree, we find true and false negative answers from the verification logic implementation at the application level.
2.1 Implementation Bug
This failure cause refers to a technical problem that shows up as a signature verification failure. The available diagnostic data may or may not categorize the failure as a bug, so this failure cause may hide itself under another one. In any event, no service is provided by the digital signature scheme in these circumstances.
2.2 Unrecognized Signature Context
In this branch of the decision tree, something other than the formal verification algorithm causes a verification failure at the application level. Somehow arbitrarily, we included minimal key size thresholds in this category; they might be considered an intrinsic component of a formal algorithm.
2.2.1 Unsupported Procedures
This failure cause includes unsupported protocols, data formats, algorithms. For reasonably well engineered signature procedures with proper documentation, this failure cause should be fixable by software upgrade or additional software development.
2.2.2 Unrecognized Public Key Material
This failure cause refer to cases where an invalidity indication is affixed to some public key material, including by default for public key material unknown in the verification software configuration. It is an abuse of language to qualify as "trusted" public key material that would not trigger this failure cause, see the decision entry 3.2.1.
2.2.3 Signature Parameters Out of Bounds
This failure cause includes dangerously short key sizes, and signature validity time limit exceeded.
2.3 Invalid Signature
This is the failure code that the digital signature theory expects, in which the verification algorithm is performed according to the scheme design, up to a point where a specific check fails.
3. Signature Verification Success Observed
In this part of the decision tree, we find true and false positive answers from the verification logic implementation at the application level. There is no match between true and false positive answers at the application level and at the formal algorithm level, as shown by the sub-entries.
3.1 Undetected Bug in the Verification Logic
This is not to be confused with a successful signature forgery attack, but it has the same practical consequences, until someone finds the bug and calls for an upgrade in the signature verification software. The RSA scheme with the public exponent 3 has experienced this situation, which does not put into question its intrinsic security.
3.2 Signature Verification Logic Success
The public key cryptography theory stops here, and is helpless about the determination of which sub-entry applies in the decision tree.
3.2.1 With Assurance of Well Behaved Signatories
Nothing in the theory assists the assurance that the signatory (or signatories) is actually well behaved. Such assurance must be gathered by other means. When a chain of security certificates is involved, the required assurance applies to the signatory at each link in the chain.
3.2.2 Without Assurance of Well Behaved Signatories
Perhaps surprisingly, this is the usual net benefit of a digital signature verification application: it shifts the integrity uncertainty from application data handling (according to the presumed application semantic) to signature private key material handling (according to generic and specific rules and guidelines for the digital signature scheme that was just validated).

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.

5.3.2 Signature Verification Procedure

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 "5.3.2.1 Verification Procedure with the Investigation Approach" and "5.3.2.2 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.

5.3.2.1 Verification Procedure with the Investigation Approach

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.

5.3.2.2 Verification Procedure with the Assumption Approach

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.

6. What's in a Name

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].

7. References

[BBS]
Blum, Leonore; Blum, Manuel; and Shub, M., "A Simple Unpredictable Pseudo-random Number Generator", SIAM Journal of Computing, vol. 15, no. 2, May 1986, pp 364-383
[BERNSTEIN-STOA]
D. J. Bernstein. "RSA signatures and Rabin-Williams signatures: the state of the art", Document ID: 5e92b45abdf8abc4e55ea02607400599, Date: 2008.01.31, available at http://cr.yp.to/papers.html#rwsota.
[BERNSTEIN-TIGHT2003]
D. J. Bernstein. "Proving tight security for Rabin-Williams signatures", draft, also Document ID: c30057d690a8fb42af6a5172b5da9006, Date: 2003.09.26, available at http://cr.yp.to/papers.html#rwtight.
[BERNSTEIN-TIGHT]
D. J. Bernstein. "Proving tight security for Rabin-Williams signatures", Pages 70-87 in "Advances in cryptology---EUROCRYPT 2008, 27th annual international conference on the theory and applications of cryptographic techniques", Istanbul, Turkey, April 13--17, 2008, proceedings, edited by Nigel Smart, Lecture Notes in Computer Science 4965, Springer, 2008. ISBN 978-3-540-78966-6, also Document ID: c30057d690a8fb42af6a5172b5da9006, Date: 2008.02.01, available at http://cr.yp.to/papers.html#rwtight.
[FIPS186-3]
NIST, "Digital Signature Standard (DSS)", FIPS 186-3, June 2009, available at http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf.
[GUILL_QUISQ]
Guillou, Louis Claude; Quisquater, Jean-Jacques; Walker, Mike; Landrock, Peter; and Shaer, Caroline, "Precautions taken against various potential attacks in ISO/IEC DIS 9796 'Digital signature scheme giving message recovery'", Advances in Cryptology, Eurocrypt'90, Lecture Notes In Computer Science no. 473, pp 465-473.
[HARN-KIESLER]
Harn, Lein, and Kiesler, T., "Improved Rabin's Scheme with High Efficiency", Electronics Letters, Vol. 25, no. 11, May 25th, 1989, pp 726-728 (see also erratum published in Electronics Letters, Vol. 25, no. 15, page 1016).
[ISO10118-4]
ISO/IEC 10118-4:1998, "Information technology -- Security techniques -- Hash-functions -- Part 4: Hash-functions using modular arithmetic".
[ISO9796-2]
ISO/IEC 9796-2:2002 "Information technology -- Security techniques -- Digital signature schemes giving message recovery -- Part 2: Integer factorization based mechanisms".
[KOBLITZ-MENEZES]
Koblitz, Neal; Menezes, Alfred, "Another Look at ``Provable Security''", Cryptology ePrint Archive: Report 2004/152, available at http://eprint.iacr.org/2004/152.pdf.
[PEKE]
Moreau, Thierry, "PEKE, Probabilistic Encryption Key Exchange, 10 Years Later, Including the PEKEv1.25 Specifications" Cryptology ePrint Archive: Report 2005/183, available at http://eprint.iacr.org/2005/183.pdf.
[PLOUFFE]
Bailey, David H.; Borwein, Peter B.; and Plouffe, Simon (April 1997), "On the Rapid Computation of Various Polylogarithmic Constants", Mathematics of Computation 66 (218): 903–913, doi:10.1090/S0025-5718-97-00856-9, available at http://crd.lbl.gov/~dhbailey/dhbpapers/digits.pdf.
[RABIN]
Rabin, Michael, "Digitalized Signatures and Public-Key Functions as Intractable as Factorization", MIT Laboratory for Computer Science, TR-212, January 1979, available at http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-212.pdf.
[RFC4055]
Schaad, J., Kaliski, B., and R. Housley, "Additional Algorithms and Identifiers for RSA Cryptography for use in the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 4055, June 2005 (available at http://www.ietf.org/rfc/rfc4055.txt).
[RSA]
Rivest, R.; A. Shamir; L. Adleman (1978), "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21 (2): 120–126, February 1978 available at http://theory.lcs.mit.edu/~rivest/rsapaper.pdf.
[SHIMADA]
Shimada, M., "Another Practical Public-Key Cryptosystem", Electronic Letters, Vol. 28, no. 23, November 5th, 1992, pp 2146.
[TS_102_176]
European Telecommunications Standards Institute (ETSI), "Electronic Signatures and Infrastructures (ESI); Algorithms and Parameters for Secure Electronic Signatures; Part 1: Hash functions and asymmetric algorithms", Document reference ETSI TS 102 176-1 V2.0.0 (2007-11).
[WILLIAMS-80]
Hugh C. Williams, "A Modification of the RSA Public Key Encryption Procedure", IEEE Transactions on Information Theory, 26 (6): pp 726-729, November 1980.
[WILLIAMS-85]
Hugh C. Williams, "An M3 Public Key Encryption Scheme", Proceedings of Crypto'85, pp 358-368.

A. Fixed Constant Value

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

B. Software Utilities Design Notes

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".

B.1 Overview and Principles

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 dec-labels and 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.

B.2 Signature Key Pair Generation

The 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:

--modulus-size <n>
The Rabin-Williams modulus size parameter, indicated here as a bit count typically in the range from 512 to 4096, is by far the most important quantitative security parameter for the signature scheme. The current conventional wisdom suggests that 1024, which is the default, should be a minimum setting except for short-term digital signature key pairs.
--entropy <rng-option>
For signature key pair generation, a secret random source is of critical importance. The entropy source option is an important aspect of secret random source quality. The specification of this parameter is implementation-dependent since entropy sources are very dependent on local computing resources.

The utility output specification is driven by a few more command line arguments:

--private-key <file>
Indicates the private signature key file to be created instead of the default utility's standard output. If specified, this file must not exist and it must be possible to create it. Its contents may be encrypted based on an encryption passphrase supplied by the user.
--public-key <file>
Indicates a signature public key file to be created. This file must not exist and it must be possible to create it.
--format [asn1|dec|hex|dec-labels|hex-labels]
This format specification applies to the last Scirpo private signature key file (or standard output) or public key file. The default in either case is dec-labels.
--encryption <passphrase-option>
This is an implementation-defined command line argument for applying encryption protection to the private key file. Unless otherwise specified, the default is to leave the private key data in the clear.

Finally, three general-purpose command line arguments are recognized:

--verbose <debug-level>
This is an implementation-defined command line argument for adjustment in the verbosity level.
--help
Displays a utility user help message.
--warranty
Displays an implementation-defined user message, presumably a placeholder for some legalese that denies any liability from the part of the utility software provider, and accessorily describes the legitimate user's intellectual property rights if any.

B.3 Signature Generation

The 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:

--private-key <file>
Indicates a Scirpo private signature key file to be used for signature generation. This file must be available for read but it may require a decryption passphrase supplied by the user.
--format [asn1|dec|hex|dec-labels|hex-labels]
This format specification applies to the preceding Scirpo private signature key file. The default is derived by the utility from the file contents.
--encryption <passphrase-option>
This is an implementation-defined command line argument for decrypting the private key file. Unless otherwise specified, the default is to expect private key data in the clear.

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:

--input <file>
Indicates the data file to be signed instead of the default utility's standard input. This file must be available for read. End-of-line marker conversion is implementation-defined, but the file should be considered analogous to a binary file if no other specification is provided.
--hash [sha1|sha224|sha256]
Indicates a secure hash function that the signature generation utility should use for signature generation. The default is sha256.
--salt-size <n>
Indicates the salt bit count that the signature generation utility should use for signature generation. Must be a multiple of 8. The default is 64 bits.
--root-select [quad|sa|abs-quad|sb|sc|sd]
This command line argument refers to the selection of a signature solution among sA, sB, sC, and sD in the document section "5.2 Signature Operation". The argument quad is a synonym for sa and corresponds to the strategy "always sA". The argument abs_quad corresponds 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 quad should 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 quad, sa, abs-quad, or sd and one of sb or 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:

--signature <file>
Indicates the signature file to be created instead of the default utility's standard output. If specified, this file must not exist and it must be possible to create it.
--format [asn1|dec|hex|dec-labels|hex-labels]
This format specification applies to the preceding signature file (or standard output). The default is dec-labels.
--embed-public-key or --no-embed-public-key
This option indicates whether the utility will put a copy of the signature public key within the signature file to be created (the public key must be known at verification time, and the public key data is embedded within the signature file or explicitly indicated as a public key file).
--t-in-signature
This command line option requests a signature file with the optional T value added to the essential signature field. See the end of section "5.2 Signature Operation".
--j-in-signature
This command line option requests a signature file with the optional J value added to the essential signature field; it is allowed only when the optional T value is also added. See the end of section "5.2 Signature Operation".

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:

--out-private-key <file>
Indicates the private signature key file to be created. This file must not exist and it must be possible to create it. Its contents may be encrypted based on an encryption passphrase supplied by the user.
--format [asn1|dec|hex|dec-labels|hex-labels]
This format specification applies to the preceding Scirpo private signature key file. The default is dec-labels.
--encryption <passphrase-option>
This is an implementation-defined command line argument for applying encryption protection to the private key file. Unless otherwise specified, the default is to leave the private key data in the clear.

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:

--out-public-key <file>
Indicates the public key file to be created. This file must not exist and it must be possible to create it.
--format [asn1|dec|hex|dec-labels|hex-labels]
This format specification applies to the preceding public key file. The default is dec-labels.

Finally, four general-purpose command line arguments are recognized:

--entropy <rng-option>
For the signature generation utility, a secret random source is important but not as critical as for the signature key pair generation utility. This argument does not apply to the special operating mode where public key data representation is created. The entropy source option is an important aspect of secret random source quality. The specification of this parameter is implementation-dependent since entropy sources are very dependent on local computing resources.
--verbose <debug-level>
This is an implementation-defined command line argument for adjustment in the verbosity level.
--help
Displays a utility user help message.
--warranty
Displays an implementation-defined user message, presumably a placeholder for some legalese that denies any liability from the part of the utility software provider, and accessorily describes the legitimate user's intellectual property rights if any.

B.4 Signature Verification

The 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:

--signature <file>
Indicates a Scirpo signature file to be verified. This file must be available for read.
--format [asn1|dec|hex|dec-labels|hex-labels]
This format specification applies to the preceding Scirpo signature file. The default is derived by the utility from the file contents.
--meta-data <file>
Indicates a meta-data file to be inspected for occurrences of scirpo signatures in any supported encoding. This file must be available for read.

The verification utility must be told about the public signature keys it should handle.

--embedded-public-keys
This option indicates that signature verification should occur for Scirpo signatures having an embedded public key. This option semantic is assumed by default, but when the option is present the explicit public key files are not allowed.
--public-key <file>
Indicates an explicit public key file. More than one occurrence of this argument may be provided, in which case a signature using any of the indicated public keys may be verified. These files must be available for read. Even in the presence of the --no-other-public-keys option, the verified signatures may embed a public key also sepcified in one of the explicit public key files.
--format [asn1|dec|hex|dec-labels|hex-labels]
This format specification applies to the last public key file encountered in the command line arguments. The default is derived by the utility from the file contents.
--other-public-keys or --no-other-public-keys
These options indicate whether a Scirpo signature is to be validated if it contains a public key not present 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.

--input <file>
Indicates the alledgedly signed data file instead of the default utility's standard input. This file must be available for read. End-of-line marker conversion is implementation-defined, but the file should be considered analogous to a binary file if no other specification is provided.
[--hash [sha1|sha224|sha256]]...
This command line argument indicates a secure hash function that the verification utility should accept. This argument may be repeated multiple times if more than one hash functions are supported and considered secure.
--modulus-size <n>
Indicates the minimum Rabin-Williams modulus size that the verification utility should accept. The unit is bits, and the default is 512.
--salt-size <n>
Indicates the minimum salt size that the verification utility should accept. The unit is bits, and the default is 32.
--inspect-public-key or --no-inspect-public-key
Indicates whether the Rabin-Williams modulus parameter should be checked. The default is yes, which causes the utility to verify that the modulus value is a composite number.

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.

--output <file>
Tells the output file to be used instead of the default utility's standard output.
--output-format [1|m|k|h|s|c|p|l|f]...
Indicates the fields to be present on a line of output reporting a verified signature. The letters or digit are concatenated in the command line argument, and the corresponding output fields are separated by commas in the utility output; 1 is the fixed text signed, m is the public key modulus value in hexadecimal notation, k is the public key modulus size as a decimal bit count, h is an indication for the hash function that verified the signature, s is the salt size as a decimal bit count, c is the fixed text Scirpo intended for future expansion where the utility would recognize signatures complying to other schemes, p is the position (byte offset) of signature data within the meta-data input file, l is the length (byte count) of signature data within the meta-data input file, and f is the format (same keywords as for the option --format) of signature data within the meta-data input file. The default value is m and 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:

--out-signature <file>
Indicates the signature file to be created. This file must not exist and it must be possible to create it.
--format [asn1|dec|hex|dec-labels|hex-labels]
This format specification applies to the preceding signature file. The default is dec-labels.
--embed-public-key or --no-embed-public-key
This option indicates whether the utility will put a copy of the signature public key within the signature file to be created.
--t-in-signature
This command line option requests a signature file with the optional T value added to the essential signature field. See the end of section "5.2 Signature Operation".
--j-in-signature
This command line option requests a signature file with the optional J value added to the essential signature field; it is allowed only when the optional T value is also added. See the end of section "5.2 Signature Operation".

Finally, three general-purpose command line arguments are recognized:

--verbose <debug-level>
This is an implementation-defined command line argument for adjustment in the verbosity level.
--help
Displays a utility user help message.
--warranty
Displays an implementation-defined user message, presumably a placeholder for some legalese that denies any liability from the part of the utility software provider, and accessorily describes the legitimate user's intellectual property rights if any.