Add signature generation operation classes. Remove sign() from

PK_Signing_Key, though for the moment the class remains because there
are a few pieces of code that use it to detect if signatures are
supported, or for passing to functions in look_pk

20 files changed, 474 insertions, 72 deletions

diff --git a/src/engine/def_engine/def_pk_ops.cpp b/src/engine/def_engine/def_pk_ops.cpp
index b2f53376d..d1ee454a2 100644
--- a/src/engine/def_engine/def_pk_ops.cpp
+++ b/src/engine/def_engine/def_pk_ops.cpp
@@ -1,6 +1,6 @@
 /*
 * PK Operations
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2010 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -23,6 +23,34 @@
   #include <botan/elg_op.h>
 #endif
 
+#if defined(BOTAN_HAS_RSA)
+  #include <botan/rsa.h>
+#endif
+
+#if defined(BOTAN_HAS_RW)
+  #include <botan/rw.h>
+#endif
+
+#if defined(BOTAN_HAS_DSA)
+  #include <botan/dsa.h>
+#endif
+
+#if defined(BOTAN_HAS_ECDSA)
+  #include <botan/ecdsa.h>
+#endif
+
+#if defined(BOTAN_HAS_ELGAMAL)
+  #include <botan/elgamal.h>
+#endif
+
+#if defined(BOTAN_HAS_GOST_3410_2001)
+  #include <botan/gost_3410.h>
+#endif
+
+#if defined(BOTAN_HAS_NYBERG_RUEPPEL)
+  #include <botan/nr.h>
+#endif
+
 #if defined(BOTAN_HAS_DIFFIE_HELLMAN)
   #include <botan/dh.h>
 #endif
@@ -49,6 +77,43 @@ Default_Engine::get_key_agreement_op(const Private_Key& key) const
    return 0;
    }
 
+PK_Ops::Signature_Operation*
+Default_Engine::get_signature_op(const Private_Key& key) const
+   {
+#if defined(BOTAN_HAS_RSA)
+   if(const RSA_PrivateKey* s = dynamic_cast<const RSA_PrivateKey*>(&key))
+      return new RSA_Signature_Operation(*s);
+#endif
+
+#if defined(BOTAN_HAS_RW)
+   if(const RW_PrivateKey* s = dynamic_cast<const RW_PrivateKey*>(&key))
+      return new RW_Signature_Operation(*s);
+#endif
+
+#if defined(BOTAN_HAS_DSA)
+   if(const DSA_PrivateKey* s = dynamic_cast<const DSA_PrivateKey*>(&key))
+      return new DSA_Signature_Operation(*s);
+#endif
+
+#if defined(BOTAN_HAS_ECDSA)
+   if(const ECDSA_PrivateKey* s = dynamic_cast<const ECDSA_PrivateKey*>(&key))
+      return new ECDSA_Signature_Operation(*s);
+#endif
+
+#if defined(BOTAN_HAS_GOST_3410_2001)
+   if(const GOST_3410_PrivateKey* s =
+         dynamic_cast<const GOST_3410_PrivateKey*>(&key))
+      return new GOST_3410_Signature_Operation(*s);
+#endif
+
+#if defined(BOTAN_HAS_NYBERG_RUEPPEL)
+   if(const NR_PrivateKey* s = dynamic_cast<const NR_PrivateKey*>(&key))
+      return new NR_Signature_Operation(*s);
+#endif
+
+   return 0;
+   }
+
 #if defined(BOTAN_HAS_IF_PUBLIC_KEY_FAMILY)
 /*
 * Acquire an IF op
diff --git a/src/engine/def_engine/default_engine.h b/src/engine/def_engine/default_engine.h
index 918a42114..9f18ca469 100644
--- a/src/engine/def_engine/default_engine.h
+++ b/src/engine/def_engine/default_engine.h
@@ -20,7 +20,11 @@ class Default_Engine : public Engine
    public:
       std::string provider_name() const { return "core"; }
 
-      PK_Ops::KA_Operation* get_key_agreement_op(const Private_Key&) const;
+      PK_Ops::KA_Operation*
+         get_key_agreement_op(const Private_Key& key) const;
+
+      PK_Ops::Signature_Operation*
+         get_signature_op(const Private_Key& key) const;
 
 #if defined(BOTAN_HAS_IF_PUBLIC_KEY_FAMILY)
       IF_Operation* if_op(const BigInt&, const BigInt&, const BigInt&,
diff --git a/src/engine/engine.h b/src/engine/engine.h
index ea9c05997..6087af52c 100644
--- a/src/engine/engine.h
+++ b/src/engine/engine.h
@@ -84,6 +84,12 @@ class BOTAN_DLL Engine
          return 0;
          }
 
+      virtual PK_Ops::Signature_Operation*
+         get_signature_op(const Private_Key&) const
+         {
+         return 0;
+         }
+
 #if defined(BOTAN_HAS_IF_PUBLIC_KEY_FAMILY)
       virtual IF_Operation* if_op(const BigInt&, const BigInt&, const BigInt&,
                                   const BigInt&, const BigInt&, const BigInt&,
diff --git a/src/pubkey/dsa/dsa.cpp b/src/pubkey/dsa/dsa.cpp
index 91adb83d4..403243a97 100644
--- a/src/pubkey/dsa/dsa.cpp
+++ b/src/pubkey/dsa/dsa.cpp
@@ -109,4 +109,37 @@ bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    return true;
    }
 
+DSA_Signature_Operation::DSA_Signature_Operation(const DSA_PrivateKey& dsa) :
+   q(dsa.group_q()),
+   x(dsa.get_x()),
+   powermod_g_p(dsa.group_g(), dsa.group_p()),
+   mod_q(dsa.group_q())
+   {
+   }
+
+SecureVector<byte> DSA_Signature_Operation::sign(const byte msg[],
+                                                 u32bit msg_len,
+                                                 RandomNumberGenerator& rng)
+   {
+   rng.add_entropy(msg, msg_len);
+
+   BigInt k;
+   do
+      k.randomize(rng, q.bits());
+   while(k >= q);
+
+   BigInt i(msg, msg_len);
+
+   BigInt r = mod_q.reduce(powermod_g_p(k));
+   BigInt s = mod_q.multiply(inverse_mod(k, q), mul_add(x, r, i));
+
+   if(r.is_zero() || s.is_zero())
+      throw Internal_Error("DSA signature gen failure: r or s was zero");
+
+   SecureVector<byte> output(2*q.bytes());
+   r.binary_encode(output + (output.size() / 2 - r.bytes()));
+   s.binary_encode(output + (output.size() - s.bytes()));
+   return output;
+   }
+
 }
diff --git a/src/pubkey/dsa/dsa.h b/src/pubkey/dsa/dsa.h
index 8caa24b6b..444b3a825 100644
--- a/src/pubkey/dsa/dsa.h
+++ b/src/pubkey/dsa/dsa.h
@@ -9,6 +9,9 @@
 #define BOTAN_DSA_H__
 
 #include <botan/dl_algo.h>
+#include <botan/pk_ops.h>
+#include <botan/reducer.h>
+#include <botan/pow_mod.h>
 #include <botan/dsa_core.h>
 
 namespace Botan {
@@ -51,11 +54,6 @@ class BOTAN_DLL DSA_PrivateKey : public DSA_PublicKey,
                                  public virtual DL_Scheme_PrivateKey
    {
    public:
-      SecureVector<byte> sign(const byte hash[], u32bit hash_len,
-                              RandomNumberGenerator& rng) const;
-
-      bool check_key(RandomNumberGenerator& rng, bool strong) const;
-
       DSA_PrivateKey(const AlgorithmIdentifier& alg_id,
                      const MemoryRegion<byte>& key_bits,
                      RandomNumberGenerator& rng);
@@ -63,6 +61,29 @@ class BOTAN_DLL DSA_PrivateKey : public DSA_PublicKey,
       DSA_PrivateKey(RandomNumberGenerator& rng,
                      const DL_Group& group,
                      const BigInt& private_key = 0);
+
+      bool check_key(RandomNumberGenerator& rng, bool strong) const;
+
+      SecureVector<byte> sign(const byte hash[], u32bit hash_len,
+                              RandomNumberGenerator& rng) const;
+   };
+
+class BOTAN_DLL DSA_Signature_Operation : public PK_Ops::Signature_Operation
+   {
+   public:
+      DSA_Signature_Operation(const DSA_PrivateKey& dsa);
+
+      u32bit message_parts() const { return 2; }
+      u32bit message_part_size() const { return q.bytes(); }
+      u32bit max_input_bits() const { return q.bits(); }
+
+      SecureVector<byte> sign(const byte msg[], u32bit msg_len,
+                              RandomNumberGenerator& rng);
+   private:
+      const BigInt& q;
+      const BigInt& x;
+      Fixed_Base_Power_Mod powermod_g_p;
+      Modular_Reducer mod_q;
    };
 
 }
diff --git a/src/pubkey/ecdsa/ecdsa.cpp b/src/pubkey/ecdsa/ecdsa.cpp
index d245543f7..6ca3fb9b1 100644
--- a/src/pubkey/ecdsa/ecdsa.cpp
+++ b/src/pubkey/ecdsa/ecdsa.cpp
@@ -71,4 +71,40 @@ SecureVector<byte> ECDSA_PrivateKey::sign(const byte msg[],
    return output;
    }
 
+ECDSA_Signature_Operation::ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa) :
+   base_point(ecdsa.domain().get_base_point()),
+   order(ecdsa.domain().get_order()),
+   x(ecdsa.private_value())
+   {
+   }
+
+SecureVector<byte> ECDSA_Signature_Operation::sign(const byte msg[],
+                                                   u32bit msg_len,
+                                                   RandomNumberGenerator& rng)
+   {
+   rng.add_entropy(msg, msg_len);
+
+   BigInt k;
+   do
+      k.randomize(rng, order.bits()-1);
+   while(k >= order);
+
+   BigInt e(msg, msg_len);
+
+   PointGFp k_times_P = base_point * k;
+   BigInt r = k_times_P.get_affine_x() % order;
+
+   if(r == 0)
+      throw Internal_Error("ECDSA_Signature_Operation: r was zero");
+
+   BigInt k_inv = inverse_mod(k, order);
+
+   BigInt s = (((r * x) + e) * k_inv) % order;
+
+   SecureVector<byte> output(2*order.bytes());
+   r.binary_encode(output + (output.size() / 2 - r.bytes()));
+   s.binary_encode(output + (output.size() - s.bytes()));
+   return output;
+   }
+
 }
diff --git a/src/pubkey/ecdsa/ecdsa.h b/src/pubkey/ecdsa/ecdsa.h
index 53d17e304..a54b28b46 100644
--- a/src/pubkey/ecdsa/ecdsa.h
+++ b/src/pubkey/ecdsa/ecdsa.h
@@ -11,6 +11,7 @@
 #define BOTAN_ECDSA_KEY_H__
 
 #include <botan/ecc_key.h>
+#include <botan/pk_ops.h>
 
 namespace Botan {
 
@@ -107,6 +108,24 @@ class BOTAN_DLL ECDSA_PrivateKey : public ECDSA_PublicKey,
                               RandomNumberGenerator& rng) const;
    };
 
+class BOTAN_DLL ECDSA_Signature_Operation : public PK_Ops::Signature_Operation
+   {
+   public:
+      ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa);
+
+      SecureVector<byte> sign(const byte msg[], u32bit msg_len,
+                              RandomNumberGenerator& rng);
+
+      u32bit message_parts() const { return 2; }
+      u32bit message_part_size() const { return order.bytes(); }
+      u32bit max_input_bits() const { return order.bits(); }
+
+   private:
+      const PointGFp& base_point;
+      const BigInt& order;
+      const BigInt& x;
+   };
+
 }
 
 #endif
diff --git a/src/pubkey/gost_3410/gost_3410.cpp b/src/pubkey/gost_3410/gost_3410.cpp
index 25e975784..ef0bac726 100644
--- a/src/pubkey/gost_3410/gost_3410.cpp
+++ b/src/pubkey/gost_3410/gost_3410.cpp
@@ -141,4 +141,45 @@ GOST_3410_PrivateKey::sign(const byte msg[],
    return output;
    }
 
+GOST_3410_Signature_Operation::GOST_3410_Signature_Operation(
+   const GOST_3410_PrivateKey& gost_3410) :
+
+   base_point(gost_3410.domain().get_base_point()),
+   order(gost_3410.domain().get_order()),
+   x(gost_3410.private_value())
+   {
+   }
+
+SecureVector<byte> GOST_3410_Signature_Operation::sign(const byte msg[],
+                                                 u32bit msg_len,
+                                                 RandomNumberGenerator& rng)
+   {
+   BigInt k;
+   do
+      k.randomize(rng, order.bits()-1);
+   while(k >= order);
+
+   BigInt e(msg, msg_len);
+
+   e %= order;
+   if(e == 0)
+      e = 1;
+
+   PointGFp k_times_P = base_point * k;
+   k_times_P.check_invariants();
+
+   BigInt r = k_times_P.get_affine_x() % order;
+
+   BigInt s = (r*x + k*e) % order;
+
+   if(r == 0 || s == 0)
+      throw Invalid_State("GOST 34.10: r == 0 || s == 0");
+
+   SecureVector<byte> output(2*order.bytes());
+   r.binary_encode(output + (output.size() / 2 - r.bytes()));
+   s.binary_encode(output + (output.size() - s.bytes()));
+   return output;
+   }
+
+
 }
diff --git a/src/pubkey/gost_3410/gost_3410.h b/src/pubkey/gost_3410/gost_3410.h
index 669ed130f..1bf55aa21 100644
--- a/src/pubkey/gost_3410/gost_3410.h
+++ b/src/pubkey/gost_3410/gost_3410.h
@@ -2,7 +2,7 @@
 * GOST 34.10-2001
 * (C) 2007 Falko Strenzke, FlexSecure GmbH
 *          Manuel Hartl, FlexSecure GmbH
-* (C) 2008-2009 Jack Lloyd
+* (C) 2008-2010 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -11,6 +11,7 @@
 #define BOTAN_GOST_3410_KEY_H__
 
 #include <botan/ecc_key.h>
+#include <botan/pk_ops.h>
 
 namespace Botan {
 
@@ -116,6 +117,20 @@ class BOTAN_DLL GOST_3410_PrivateKey : public GOST_3410_PublicKey,
                               RandomNumberGenerator& rng) const;
    };
 
+class BOTAN_DLL GOST_3410_Signature_Operation : public PK_Ops::Signature_Operation
+   {
+   public:
+      GOST_3410_Signature_Operation(const GOST_3410_PrivateKey& gost_3410);
+
+      SecureVector<byte> sign(const byte msg[], u32bit msg_len,
+                              RandomNumberGenerator& rng);
+
+   private:
+      const PointGFp& base_point;
+      const BigInt& order;
+      const BigInt& x;
+   };
+
 }
 
 #endif
diff --git a/src/pubkey/if_algo/if_algo.h b/src/pubkey/if_algo/if_algo.h
index cbcdb9c5c..d35c8245f 100644
--- a/src/pubkey/if_algo/if_algo.h
+++ b/src/pubkey/if_algo/if_algo.h
@@ -11,6 +11,7 @@
 #include <botan/if_core.h>
 #include <botan/x509_key.h>
 #include <botan/pkcs8.h>
+#include <botan/pk_ops.h>
 
 namespace Botan {
 
@@ -92,6 +93,10 @@ class BOTAN_DLL IF_Scheme_PrivateKey : public virtual IF_Scheme_PublicKey,
       */
       const BigInt& get_d() const { return d; }
 
+      const BigInt& get_c() const { return c; }
+      const BigInt& get_d1() const { return d1; }
+      const BigInt& get_d2() const { return d2; }
+
       MemoryVector<byte> pkcs8_private_key() const;
 
    protected:
diff --git a/src/pubkey/nr/nr.cpp b/src/pubkey/nr/nr.cpp
index cdcaf3af3..08ed6b376 100644
--- a/src/pubkey/nr/nr.cpp
+++ b/src/pubkey/nr/nr.cpp
@@ -1,6 +1,6 @@
 /*
 * Nyberg-Rueppel
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2010 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -115,4 +115,39 @@ bool NR_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    return true;
    }
 
+NR_Signature_Operation::NR_Signature_Operation(const NR_PrivateKey& nr) :
+   q(nr.group_q()),
+   x(nr.get_x()),
+   powermod_g_p(nr.group_g(), nr.group_p()),
+   mod_q(nr.group_q())
+   {
+   }
+
+SecureVector<byte> NR_Signature_Operation::sign(const byte msg[],
+                                                u32bit msg_len,
+                                                RandomNumberGenerator& rng)
+   {
+   rng.add_entropy(msg, msg_len);
+
+   BigInt k;
+   do
+      k.randomize(rng, q.bits());
+   while(k >= q);
+
+   BigInt f(msg, msg_len);
+
+   if(f >= q)
+      throw Invalid_Argument("NR_Signature_Operation: Input is out of range");
+
+   BigInt c = mod_q.reduce(powermod_g_p(k) + f);
+   if(c.is_zero())
+      throw Internal_Error("Default_NR_Op::sign: c was zero");
+   BigInt d = mod_q.reduce(k - x * c);
+
+   SecureVector<byte> output(2*q.bytes());
+   c.binary_encode(output + (output.size() / 2 - c.bytes()));
+   d.binary_encode(output + (output.size() - d.bytes()));
+   return output;
+   }
+
 }
diff --git a/src/pubkey/nr/nr.h b/src/pubkey/nr/nr.h
index 1479ef064..013f3d42b 100644
--- a/src/pubkey/nr/nr.h
+++ b/src/pubkey/nr/nr.h
@@ -9,6 +9,7 @@
 #define BOTAN_NYBERG_RUEPPEL_H__
 
 #include <botan/dl_algo.h>
+#include <botan/pk_ops.h>
 #include <botan/nr_core.h>
 
 namespace Botan {
@@ -24,11 +25,11 @@ class BOTAN_DLL NR_PublicKey : public PK_Verifying_with_MR_Key,
 
       SecureVector<byte> verify(const byte sig[], u32bit sig_len) const;
 
-      u32bit max_input_bits() const { return (group_q().bits() - 1); }
-
       DL_Group::Format group_format() const { return DL_Group::ANSI_X9_57; }
+
       u32bit message_parts() const { return 2; }
       u32bit message_part_size() const { return group_q().bytes(); }
+      u32bit max_input_bits() const { return (group_q().bits() - 1); }
 
       NR_PublicKey(const AlgorithmIdentifier& alg_id,
                    const MemoryRegion<byte>& key_bits);
@@ -61,6 +62,24 @@ class BOTAN_DLL NR_PrivateKey : public NR_PublicKey,
                     const BigInt& x = 0);
    };
 
+class BOTAN_DLL NR_Signature_Operation : public PK_Ops::Signature_Operation
+   {
+   public:
+      NR_Signature_Operation(const NR_PrivateKey& nr);
+
+      u32bit message_parts() const { return 2; }
+      u32bit message_part_size() const { return q.bytes(); }
+      u32bit max_input_bits() const { return (q.bits() - 1); }
+
+      SecureVector<byte> sign(const byte msg[], u32bit msg_len,
+                              RandomNumberGenerator& rng);
+   private:
+      const BigInt& q;
+      const BigInt& x;
+      Fixed_Base_Power_Mod powermod_g_p;
+      Modular_Reducer mod_q;
+   };
+
 }
 
 #endif
diff --git a/src/pubkey/pk_keys.h b/src/pubkey/pk_keys.h
index c37ce46a5..caf1a7c9c 100644
--- a/src/pubkey/pk_keys.h
+++ b/src/pubkey/pk_keys.h
@@ -125,10 +125,6 @@ class BOTAN_DLL PK_Decrypting_Key : public virtual Private_Key
 */
 class BOTAN_DLL PK_Signing_Key : public virtual Private_Key
    {
-   public:
-      virtual SecureVector<byte> sign(const byte[], u32bit,
-                                      RandomNumberGenerator& rng) const = 0;
-      virtual ~PK_Signing_Key() {}
    };
 
 /**
diff --git a/src/pubkey/pk_ops.h b/src/pubkey/pk_ops.h
index 2b9ac4366..5aa50efdb 100644
--- a/src/pubkey/pk_ops.h
+++ b/src/pubkey/pk_ops.h
@@ -9,11 +9,46 @@
 #define BOTAN_PK_OPERATIONS_H__
 
 #include <botan/secmem.h>
+#include <botan/rng.h>
 
 namespace Botan {
 
 namespace PK_Ops {
 
+class Signature_Operation
+   {
+   public:
+      /**
+      * Find out the number of message parts supported by this scheme.
+      * @return the number of message parts
+      */
+      virtual u32bit message_parts() const { return 1; }
+
+      /**
+      * Find out the message part size supported by this scheme/key.
+      * @return the size of the message parts
+      */
+      virtual u32bit message_part_size() const { return 0; }
+
+      /**
+      * Get the maximum message size in bits supported by this public key.
+      * @return the maximum message in bits
+      */
+      virtual u32bit max_input_bits() const = 0;
+
+      /*
+      * Perform a signature operation
+      * @param msg the message
+      * @param msg_len the length of msg in bytes
+      * @param rng a random number generator
+      */
+      virtual SecureVector<byte> sign(const byte msg[],
+                                      u32bit msg_len,
+                                      RandomNumberGenerator& rng) = 0;
+
+      virtual ~Signature_Operation() {}
+   };
+
 /*
 * A generic Key Agreement Operation (eg DH or ECDH)
 */
diff --git a/src/pubkey/pubkey.cpp b/src/pubkey/pubkey.cpp
index 6932caa34..dc4e6e1b1 100644
--- a/src/pubkey/pubkey.cpp
+++ b/src/pubkey/pubkey.cpp
@@ -122,21 +122,23 @@ SecureVector<byte> PK_Decryptor_MR_with_EME::dec(const byte msg[],
 /*
 * PK_Signer Constructor
 */
-PK_Signer::PK_Signer(const PK_Signing_Key& k, EMSA* emsa_obj) :
-   key(k), emsa(emsa_obj)
+PK_Signer::PK_Signer(const Private_Key& key, EMSA* emsa_obj) :
+   emsa(emsa_obj)
    {
-   sig_format = IEEE_1363;
-   }
+   Algorithm_Factory::Engine_Iterator i(global_state().algorithm_factory());
 
-/*
-* Set the signature format
-*/
-void PK_Signer::set_output_format(Signature_Format format)
-   {
-   if(key.message_parts() == 1 && format != IEEE_1363)
-      throw Invalid_State("PK_Signer: Cannot set the output format for " +
-                          key.algo_name() + " keys");
-   sig_format = format;
+   while(const Engine* engine = i.next())
+      {
+      op = engine->get_signature_op(key);
+      if(op)
+         break;
+      }
+
+   if(op == 0)
+      throw Lookup_Error("PK_Signer: No working engine for " +
+                         key.algo_name());
+
+   sig_format = IEEE_1363;
    }
 
 /*
@@ -150,15 +152,6 @@ SecureVector<byte> PK_Signer::sign_message(const byte msg[], u32bit length,
    }
 
 /*
-* Sign a message
-*/
-SecureVector<byte> PK_Signer::sign_message(const MemoryRegion<byte>& msg,
-                                           RandomNumberGenerator& rng)
-   {
-   return sign_message(msg, msg.size(), rng);
-   }
-
-/*
 * Add more to the message to be signed
 */
 void PK_Signer::update(const byte in[], u32bit length)
@@ -167,42 +160,26 @@ void PK_Signer::update(const byte in[], u32bit length)
    }
 
 /*
-* Add more to the message to be signed
-*/
-void PK_Signer::update(byte in)
-   {
-   update(&in, 1);
-   }
-
-/*
-* Add more to the message to be signed
-*/
-void PK_Signer::update(const MemoryRegion<byte>& in)
-   {
-   update(in, in.size());
-   }
-
-/*
 * Create a signature
 */
 SecureVector<byte> PK_Signer::signature(RandomNumberGenerator& rng)
    {
    SecureVector<byte> encoded = emsa->encoding_of(emsa->raw_data(),
-                                                  key.max_input_bits(),
+                                                  op->max_input_bits(),
                                                   rng);
 
-   SecureVector<byte> plain_sig = key.sign(encoded, encoded.size(), rng);
+   SecureVector<byte> plain_sig = op->sign(encoded, encoded.size(), rng);
 
-   if(key.message_parts() == 1 || sig_format == IEEE_1363)
+   if(op->message_parts() == 1 || sig_format == IEEE_1363)
       return plain_sig;
 
    if(sig_format == DER_SEQUENCE)
       {
-      if(plain_sig.size() % key.message_parts())
+      if(plain_sig.size() % op->message_parts())
          throw Encoding_Error("PK_Signer: strange signature size found");
-      const u32bit SIZE_OF_PART = plain_sig.size() / key.message_parts();
+      const u32bit SIZE_OF_PART = plain_sig.size() / op->message_parts();
 
-      std::vector<BigInt> sig_parts(key.message_parts());
+      std::vector<BigInt> sig_parts(op->message_parts());
       for(u32bit j = 0; j != sig_parts.size(); ++j)
          sig_parts[j].binary_decode(plain_sig + SIZE_OF_PART*j, SIZE_OF_PART);
 
diff --git a/src/pubkey/pubkey.h b/src/pubkey/pubkey.h
index 4d6490919..fc0e90fa8 100644
--- a/src/pubkey/pubkey.h
+++ b/src/pubkey/pubkey.h
@@ -112,13 +112,14 @@ class BOTAN_DLL PK_Signer
       * @return the signature
       */
       SecureVector<byte> sign_message(const MemoryRegion<byte>& in,
-                                      RandomNumberGenerator& rng);
+                                      RandomNumberGenerator& rng)
+         { return sign_message(&in[0], in.size(), rng); }
 
       /**
       * Add a message part (single byte).
       * @param the byte to add
       */
-      void update(byte in);
+      void update(byte in) { update(&in, 1); }
 
       /**
       * Add a message part.
@@ -131,7 +132,7 @@ class BOTAN_DLL PK_Signer
       * Add a message part.
       * @param in the message part to add
       */
-      void update(const MemoryRegion<byte>& in);
+      void update(const MemoryRegion<byte>& in) { update(&in[0], in.size()); }
 
       /**
       * Get the signature of the so far processed message (provided by the
@@ -145,7 +146,7 @@ class BOTAN_DLL PK_Signer
       * Set the output format of the signature.
       * @param format the signature format to use
       */
-      void set_output_format(Signature_Format format);
+      void set_output_format(Signature_Format format) { sig_format = format; }
 
       /**
       * Construct a PK Signer.
@@ -153,16 +154,16 @@ class BOTAN_DLL PK_Signer
       * @param emsa the EMSA to use
       * An example would be "EMSA1(SHA-224)".
       */
-      PK_Signer(const PK_Signing_Key& key, EMSA* emsa);
+      PK_Signer(const Private_Key& key, EMSA* emsa);
 
-      ~PK_Signer() { delete emsa; }
+      ~PK_Signer() { delete op; delete emsa; }
    private:
       PK_Signer(const PK_Signer&);
       PK_Signer& operator=(const PK_Signer&);
 
-      const PK_Signing_Key& key;
-      Signature_Format sig_format;
+      PK_Ops::Signature_Operation* op;
       EMSA* emsa;
+      Signature_Format sig_format;
    };
 
 /**
diff --git a/src/pubkey/rsa/rsa.cpp b/src/pubkey/rsa/rsa.cpp
index b181cb9cc..72a99b4f7 100644
--- a/src/pubkey/rsa/rsa.cpp
+++ b/src/pubkey/rsa/rsa.cpp
@@ -138,4 +138,29 @@ bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    return true;
    }
 
+RSA_Signature_Operation::RSA_Signature_Operation(const RSA_PrivateKey& rsa) :
+   q(rsa.get_q()),
+   c(rsa.get_c()),
+   powermod_d1_p(rsa.get_d1(), rsa.get_p()),
+   powermod_d2_q(rsa.get_d2(), rsa.get_q()),
+   mod_p(rsa.get_p()),
+   n_bits(rsa.get_n().bits())
+   {
+   }
+
+SecureVector<byte> RSA_Signature_Operation::sign(const byte msg[],
+                                                 u32bit msg_len,
+                                                 RandomNumberGenerator& rng)
+   {
+   const u32bit n_bytes = (n_bits + 7) / 8;
+
+   BigInt i(msg, msg_len);
+   BigInt j1 = powermod_d1_p(i);
+   BigInt j2 = powermod_d2_q(i);
+
+   j1 = mod_p.reduce(sub_mul(j1, j2, c));
+
+   return BigInt::encode_1363(mul_add(j1, q, j2), n_bytes);
+   }
+
 }
diff --git a/src/pubkey/rsa/rsa.h b/src/pubkey/rsa/rsa.h
index 0d5a4ad2e..aa2f8124f 100644
--- a/src/pubkey/rsa/rsa.h
+++ b/src/pubkey/rsa/rsa.h
@@ -101,6 +101,23 @@ class BOTAN_DLL RSA_PrivateKey : public RSA_PublicKey,
       BigInt private_op(const byte[], u32bit) const;
    };
 
+class BOTAN_DLL RSA_Signature_Operation : public PK_Ops::Signature_Operation
+   {
+   public:
+      RSA_Signature_Operation(const RSA_PrivateKey& rsa);
+
+      u32bit max_input_bits() const { return (n_bits - 1); }
+
+      SecureVector<byte> sign(const byte msg[], u32bit msg_len,
+                              RandomNumberGenerator& rng);
+   private:
+      const BigInt& q;
+      const BigInt& c;
+      Fixed_Exponent_Power_Mod powermod_d1_p, powermod_d2_q;
+      Modular_Reducer mod_p;
+      u32bit n_bits;
+   };
+
 }
 
 #endif
diff --git a/src/pubkey/rw/rw.cpp b/src/pubkey/rw/rw.cpp
index 72fa29afa..de50313d2 100644
--- a/src/pubkey/rw/rw.cpp
+++ b/src/pubkey/rw/rw.cpp
@@ -123,4 +123,37 @@ bool RW_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
    return true;
    }
 
+RW_Signature_Operation::RW_Signature_Operation(const RW_PrivateKey& rw) :
+   q(rw.get_q()),
+   c(rw.get_c()),
+   n(rw.get_n()),
+   powermod_d1_p(rw.get_d1(), rw.get_p()),
+   powermod_d2_q(rw.get_d2(), rw.get_q()),
+   mod_p(rw.get_p())
+   {
+   }
+
+SecureVector<byte> RW_Signature_Operation::sign(const byte msg[],
+                                                u32bit msg_len,
+                                                RandomNumberGenerator&)
+   {
+   BigInt i(msg, msg_len);
+
+   if(i >= n || i % 16 != 12)
+      throw Invalid_Argument("Rabin-Williams: invalid input");
+
+   if(jacobi(i, n) != 1)
+      i >>= 1;
+
+   BigInt j1 = powermod_d1_p(i);
+   BigInt j2 = powermod_d2_q(i);
+   j1 = mod_p.reduce(sub_mul(j1, j2, c));
+
+   BigInt r = mul_add(j1, q, j2);
+
+   r = std::min(r, n - r);
+
+   return BigInt::encode_1363(r, n.bytes());
+   }
+
 }
diff --git a/src/pubkey/rw/rw.h b/src/pubkey/rw/rw.h
index efdca04e7..a46cb5bb3 100644
--- a/src/pubkey/rw/rw.h
+++ b/src/pubkey/rw/rw.h
@@ -49,11 +49,6 @@ class BOTAN_DLL RW_PrivateKey : public RW_PublicKey,
                                 public IF_Scheme_PrivateKey
    {
    public:
-      SecureVector<byte> sign(const byte[], u32bit,
-                              RandomNumberGenerator& rng) const;
-
-      bool check_key(RandomNumberGenerator& rng, bool) const;
-
       RW_PrivateKey(const AlgorithmIdentifier& alg_id,
                     const MemoryRegion<byte>& key_bits,
                     RandomNumberGenerator& rng) :
@@ -66,6 +61,30 @@ class BOTAN_DLL RW_PrivateKey : public RW_PublicKey,
          IF_Scheme_PrivateKey(rng, p, q, e, d, n) {}
 
       RW_PrivateKey(RandomNumberGenerator& rng, u32bit bits, u32bit = 2);
+
+      bool check_key(RandomNumberGenerator& rng, bool) const;
+
+      SecureVector<byte> sign(const byte[], u32bit,
+                              RandomNumberGenerator& rng) const;
+   };
+
+class BOTAN_DLL RW_Signature_Operation : public PK_Ops::Signature_Operation
+   {
+   public:
+      RW_Signature_Operation(const RW_PrivateKey& rw);
+
+      u32bit max_input_bits() const { return (n.bits() - 1); }
+
+      SecureVector<byte> sign(const byte msg[], u32bit msg_len,
+                              RandomNumberGenerator& rng);
+   private:
+      const BigInt& q;
+      const BigInt& c;
+      const BigInt& n;
+
+      Fixed_Exponent_Power_Mod powermod_d1_p, powermod_d2_q;
+      Modular_Reducer mod_p;
+      u32bit n_bits;
    };
 
 }