diff --git a/keystore/Android.mk b/keystore/Android.mk
index f495f34..47b7e84 100644
--- a/keystore/Android.mk
+++ b/keystore/Android.mk
@@ -20,7 +20,15 @@
 LOCAL_CFLAGS := -Wall -Wextra -Werror
 LOCAL_SRC_FILES := keystore.cpp keyblob_utils.cpp
 LOCAL_C_INCLUDES := external/openssl/include
-LOCAL_SHARED_LIBRARIES := libcutils libcrypto libhardware libkeystore_binder libutils liblog libbinder
+LOCAL_SHARED_LIBRARIES := \
+	libbinder \
+	libcutils \
+	libcrypto \
+	libhardware \
+	libkeystore_binder \
+	liblog \
+	libsoftkeymaster \
+	libutils
 LOCAL_MODULE := keystore
 LOCAL_MODULE_TAGS := optional
 LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
diff --git a/keystore/include/keystore/keystore.h b/keystore/include/keystore/keystore.h
index 973c447..32354df 100644
--- a/keystore/include/keystore/keystore.h
+++ b/keystore/include/keystore/keystore.h
@@ -48,7 +48,8 @@
  */
 enum {
     KEYSTORE_FLAG_NONE = 0,
-    KEYSTORE_FLAG_ENCRYPTED = 1,
+    KEYSTORE_FLAG_ENCRYPTED = 1 << 0,
+    KEYSTORE_FLAG_FALLBACK = 1 << 1,
 };
 
 /**
diff --git a/keystore/keyblob_utils.cpp b/keystore/keyblob_utils.cpp
index fd82d2a..b208073 100644
--- a/keystore/keyblob_utils.cpp
+++ b/keystore/keyblob_utils.cpp
@@ -26,9 +26,11 @@
  *
  * 4-byte SOFT_KEY_MAGIC
  *
- * 4-byte 32-bit integer big endian for public_key_length
+ * 4-byte 32-bit integer big endian for public_key_length. This may be zero
+ *     length which indicates the public key should be derived from the
+ *     private key.
  *
- * public_key_length bytes of public key
+ * public_key_length bytes of public key (may be empty)
  *
  * 4-byte 32-bit integer big endian for private_key_length
  *
diff --git a/keystore/keystore.cpp b/keystore/keystore.cpp
index 12d3b44..b4cb64d 100644
--- a/keystore/keystore.cpp
+++ b/keystore/keystore.cpp
@@ -42,6 +42,8 @@
 
 #include <hardware/keymaster.h>
 
+#include <keymaster/softkeymaster.h>
+
 #include <utils/String8.h>
 #include <utils/UniquePtr.h>
 #include <utils/Vector.h>
@@ -471,6 +473,18 @@
         }
     }
 
+    bool isFallback() const {
+        return mBlob.flags & KEYSTORE_FLAG_FALLBACK;
+    }
+
+    void setFallback(bool fallback) {
+        if (fallback) {
+            mBlob.flags |= KEYSTORE_FLAG_FALLBACK;
+        } else {
+            mBlob.flags &= ~KEYSTORE_FLAG_FALLBACK;
+        }
+    }
+
     void setVersion(uint8_t version) {
         mBlob.version = version;
     }
@@ -1004,6 +1018,23 @@
             }
         }
 
+        /*
+         * This will upgrade software-backed keys to hardware-backed keys when
+         * the HAL for the device supports the newer key types.
+         */
+        if (rc == NO_ERROR && type == TYPE_KEY_PAIR
+                && mDevice->common.module->module_api_version >= KEYMASTER_MODULE_API_VERSION_0_2
+                && keyBlob->isFallback()) {
+            ResponseCode imported = importKey(keyBlob->getValue(), keyBlob->getLength(), filename,
+                    uid, keyBlob->isEncrypted() ? KEYSTORE_FLAG_ENCRYPTED : KEYSTORE_FLAG_NONE);
+
+            // The HAL allowed the import, reget the key to have the "fresh"
+            // version.
+            if (imported == NO_ERROR) {
+                rc = get(filename, keyBlob, TYPE_KEY_PAIR, uid);
+            }
+        }
+
         if (type != TYPE_ANY && keyBlob->getType() != type) {
             ALOGW("key found but type doesn't match: %d vs %d", keyBlob->getType(), type);
             return KEY_NOT_FOUND;
@@ -1056,16 +1087,26 @@
             return SYSTEM_ERROR;
         }
 
+        bool isFallback = false;
         rc = mDevice->import_keypair(mDevice, key, keyLen, &data, &dataLength);
         if (rc) {
-            ALOGE("Error while importing keypair: %d", rc);
-            return SYSTEM_ERROR;
+            // If this is an old device HAL, try to fall back to an old version
+            if (mDevice->common.module->module_api_version < KEYMASTER_MODULE_API_VERSION_0_2) {
+                rc = openssl_import_keypair(mDevice, key, keyLen, &data, &dataLength);
+                isFallback = true;
+            }
+
+            if (rc) {
+                ALOGE("Error while importing keypair: %d", rc);
+                return SYSTEM_ERROR;
+            }
         }
 
         Blob keyBlob(data, dataLength, NULL, 0, TYPE_KEY_PAIR);
         free(data);
 
         keyBlob.setEncrypted(flags & KEYSTORE_FLAG_ENCRYPTED);
+        keyBlob.setFallback(isFallback);
 
         return put(filename, &keyBlob, uid);
     }
@@ -1688,6 +1729,7 @@
         uint8_t* data;
         size_t dataLength;
         int rc;
+        bool isFallback = false;
 
         const keymaster_device_t* device = mKeyStore->getDevice();
         if (device == NULL) {
@@ -1698,7 +1740,7 @@
             return ::SYSTEM_ERROR;
         }
 
-        if (keyType == EVP_PKEY_DSA && device->client_version >= 2) {
+        if (keyType == EVP_PKEY_DSA) {
             keymaster_dsa_keygen_params_t dsa_params;
             memset(&dsa_params, '\0', sizeof(dsa_params));
 
@@ -1734,8 +1776,13 @@
                 return ::SYSTEM_ERROR;
             }
 
-            rc = device->generate_keypair(device, TYPE_DSA, &dsa_params, &data, &dataLength);
-        } else if (keyType == EVP_PKEY_EC && device->client_version >= 2) {
+            if (device->common.module->module_api_version >= KEYMASTER_MODULE_API_VERSION_0_2) {
+                rc = device->generate_keypair(device, TYPE_DSA, &dsa_params, &data, &dataLength);
+            } else {
+                isFallback = true;
+                rc = openssl_generate_keypair(device, TYPE_DSA, &dsa_params, &data, &dataLength);
+            }
+        } else if (keyType == EVP_PKEY_EC) {
             keymaster_ec_keygen_params_t ec_params;
             memset(&ec_params, '\0', sizeof(ec_params));
 
@@ -1747,7 +1794,12 @@
             }
             ec_params.field_size = keySize;
 
-            rc = device->generate_keypair(device, TYPE_EC, &ec_params, &data, &dataLength);
+            if (device->common.module->module_api_version >= KEYMASTER_MODULE_API_VERSION_0_2) {
+                rc = device->generate_keypair(device, TYPE_EC, &ec_params, &data, &dataLength);
+            } else {
+                isFallback = true;
+                rc = openssl_generate_keypair(device, TYPE_EC, &ec_params, &data, &dataLength);
+            }
         } else if (keyType == EVP_PKEY_RSA) {
             keymaster_rsa_keygen_params_t rsa_params;
             memset(&rsa_params, '\0', sizeof(rsa_params));
@@ -1799,6 +1851,8 @@
         Blob keyBlob(data, dataLength, NULL, 0, TYPE_KEY_PAIR);
         free(data);
 
+        keyBlob.setFallback(isFallback);
+
         return mKeyStore->put(filename.string(), &keyBlob, callingUid);
     }
 
@@ -1863,8 +1917,13 @@
         params.digest_type = DIGEST_NONE;
         params.padding_type = PADDING_NONE;
 
-        rc = device->sign_data(device, &params, keyBlob.getValue(), keyBlob.getLength(),
-                data, length, out, outLength);
+        if (keyBlob.isFallback()) {
+            rc = openssl_sign_data(device, &params, keyBlob.getValue(), keyBlob.getLength(), data,
+                    length, out, outLength);
+        } else {
+            rc = device->sign_data(device, &params, keyBlob.getValue(), keyBlob.getLength(), data,
+                    length, out, outLength);
+        }
         if (rc) {
             ALOGW("device couldn't sign data");
             return ::SYSTEM_ERROR;
@@ -1910,8 +1969,13 @@
         params.digest_type = DIGEST_NONE;
         params.padding_type = PADDING_NONE;
 
-        rc = device->verify_data(device, &params, keyBlob.getValue(), keyBlob.getLength(),
-                data, dataLength, signature, signatureLength);
+        if (keyBlob.isFallback()) {
+            rc = openssl_verify_data(device, &params, keyBlob.getValue(), keyBlob.getLength(), data,
+                    dataLength, signature, signatureLength);
+        } else {
+            rc = device->verify_data(device, &params, keyBlob.getValue(), keyBlob.getLength(), data,
+                    dataLength, signature, signatureLength);
+        }
         if (rc) {
             return ::SYSTEM_ERROR;
         } else {
@@ -1958,8 +2022,14 @@
             return ::SYSTEM_ERROR;
         }
 
-        int rc = device->get_keypair_public(device, keyBlob.getValue(), keyBlob.getLength(), pubkey,
-                pubkeyLength);
+        int rc;
+        if (keyBlob.isFallback()) {
+            rc = openssl_get_keypair_public(device, keyBlob.getValue(), keyBlob.getLength(), pubkey,
+                    pubkeyLength);
+        } else {
+            rc = device->get_keypair_public(device, keyBlob.getValue(), keyBlob.getLength(), pubkey,
+                    pubkeyLength);
+        }
         if (rc) {
             return ::SYSTEM_ERROR;
         }
@@ -1997,7 +2067,7 @@
             rc = ::SYSTEM_ERROR;
         } else {
             // A device doesn't have to implement delete_keypair.
-            if (device->delete_keypair != NULL) {
+            if (device->delete_keypair != NULL && !keyBlob.isFallback()) {
                 if (device->delete_keypair(device, keyBlob.getValue(), keyBlob.getLength())) {
                     rc = ::SYSTEM_ERROR;
                 }
@@ -2210,7 +2280,7 @@
 
             if (keyBlob.getType() == ::TYPE_KEY_PAIR) {
                 // A device doesn't have to implement delete_keypair.
-                if (device->delete_keypair != NULL) {
+                if (device->delete_keypair != NULL && !keyBlob.isFallback()) {
                     if (device->delete_keypair(device, keyBlob.getValue(), keyBlob.getLength())) {
                         rc = ::SYSTEM_ERROR;
                         ALOGW("device couldn't remove %s", filename.string());
diff --git a/softkeymaster/Android.mk b/softkeymaster/Android.mk
index 8e19a93..0064d01 100644
--- a/softkeymaster/Android.mk
+++ b/softkeymaster/Android.mk
@@ -15,23 +15,27 @@
 LOCAL_PATH := $(call my-dir)
 
 include $(CLEAR_VARS)
-
 LOCAL_MODULE := keystore.default
-
 LOCAL_MODULE_PATH := $(TARGET_OUT_SHARED_LIBRARIES)/hw
-
-LOCAL_SRC_FILES := keymaster_openssl.cpp
-
+LOCAL_SRC_FILES := module.cpp
 LOCAL_C_INCLUDES := \
 	system/security/keystore \
 	external/openssl/include
-
-LOCAL_C_FLAGS = -fvisibility=hidden -Wall -Werror
-
-LOCAL_SHARED_LIBRARIES := libcrypto liblog libkeystore_binder
-
+LOCAL_CFLAGS = -fvisibility=hidden -Wall -Werror
+LOCAL_SHARED_LIBRARIES := libcrypto liblog libkeystore_binder libsoftkeymaster
 LOCAL_MODULE_TAGS := optional
-
 LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
+include $(BUILD_SHARED_LIBRARY)
 
+include $(CLEAR_VARS)
+LOCAL_MODULE := libsoftkeymaster
+LOCAL_SRC_FILES := keymaster_openssl.cpp
+LOCAL_C_INCLUDES := \
+	system/security/keystore \
+	external/openssl/include
+LOCAL_CFLAGS = -fvisibility=hidden -Wall -Werror
+LOCAL_SHARED_LIBRARIES := libcrypto liblog libkeystore_binder
+LOCAL_MODULE_TAGS := optional
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk
 include $(BUILD_SHARED_LIBRARY)
diff --git a/softkeymaster/include/keymaster/softkeymaster.h b/softkeymaster/include/keymaster/softkeymaster.h
new file mode 100644
index 0000000..7d43099
--- /dev/null
+++ b/softkeymaster/include/keymaster/softkeymaster.h
@@ -0,0 +1,46 @@
+/*
+ * Copyright 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <hardware/keymaster.h>
+
+#ifndef SOFTKEYMASTER_INCLUDE_KEYMASTER_SOFTKEYMASTER_H
+#define SOFTKEYMASTER_INCLUDE_KEYMASTER_SOFTKEYMASTER_H
+
+int openssl_generate_keypair(const keymaster_device_t* dev,
+        const keymaster_keypair_t key_type, const void* key_params,
+        uint8_t** keyBlob, size_t* keyBlobLength);
+
+int openssl_import_keypair(const keymaster_device_t* dev,
+        const uint8_t* key, const size_t key_length,
+        uint8_t** key_blob, size_t* key_blob_length);
+
+int openssl_get_keypair_public(const struct keymaster_device* dev,
+        const uint8_t* key_blob, const size_t key_blob_length,
+        uint8_t** x509_data, size_t* x509_data_length);
+
+int openssl_sign_data(const keymaster_device_t* dev,
+        const void* params,
+        const uint8_t* keyBlob, const size_t keyBlobLength,
+        const uint8_t* data, const size_t dataLength,
+        uint8_t** signedData, size_t* signedDataLength);
+
+int openssl_verify_data(const keymaster_device_t* dev,
+        const void* params,
+        const uint8_t* keyBlob, const size_t keyBlobLength,
+        const uint8_t* signedData, const size_t signedDataLength,
+        const uint8_t* signature, const size_t signatureLength);
+
+#endif /* SOFTKEYMASTER_INCLUDE_KEYMASTER_SOFTKEYMASTER_H */
diff --git a/softkeymaster/keymaster_openssl.cpp b/softkeymaster/keymaster_openssl.cpp
index 19ec999..4aaaea2 100644
--- a/softkeymaster/keymaster_openssl.cpp
+++ b/softkeymaster/keymaster_openssl.cpp
@@ -194,7 +194,6 @@
         ALOGE("public key length encoding error: size=%ld, end=%d", publicLen, end - p);
         return NULL;
     }
-    const uint8_t *pubKey = p;
 
     p += publicLen;
     if (end - p < 2) {
@@ -378,11 +377,10 @@
     return 0;
 }
 
-static int openssl_generate_keypair(const keymaster_device_t* dev,
+__attribute__ ((visibility ("default")))
+int openssl_generate_keypair(const keymaster_device_t*,
         const keymaster_keypair_t key_type, const void* key_params,
         uint8_t** keyBlob, size_t* keyBlobLength) {
-    ssize_t privateLen, publicLen;
-
     Unique_EVP_PKEY pkey(EVP_PKEY_new());
     if (pkey.get() == NULL) {
         logOpenSSLError("openssl_generate_keypair");
@@ -416,11 +414,10 @@
     return 0;
 }
 
-static int openssl_import_keypair(const keymaster_device_t* dev,
+__attribute__ ((visibility ("default")))
+int openssl_import_keypair(const keymaster_device_t*,
         const uint8_t* key, const size_t key_length,
         uint8_t** key_blob, size_t* key_blob_length) {
-    int response = -1;
-
     if (key == NULL) {
         ALOGW("input key == NULL");
         return -1;
@@ -450,7 +447,8 @@
     return 0;
 }
 
-static int openssl_get_keypair_public(const struct keymaster_device* dev,
+__attribute__ ((visibility ("default")))
+int openssl_get_keypair_public(const struct keymaster_device*,
         const uint8_t* key_blob, const size_t key_blob_length,
         uint8_t** x509_data, size_t* x509_data_length) {
 
@@ -588,16 +586,12 @@
     return 0;
 }
 
-static int openssl_sign_data(const keymaster_device_t* dev,
+__attribute__ ((visibility ("default")))
+int openssl_sign_data(const keymaster_device_t*,
         const void* params,
         const uint8_t* keyBlob, const size_t keyBlobLength,
         const uint8_t* data, const size_t dataLength,
         uint8_t** signedData, size_t* signedDataLength) {
-
-    int result = -1;
-    EVP_MD_CTX ctx;
-    size_t maxSize;
-
     if (data == NULL) {
         ALOGW("input data to sign == NULL");
         return -1;
@@ -711,7 +705,8 @@
     return result == 0 ? 0 : -1;
 }
 
-static int openssl_verify_data(const keymaster_device_t* dev,
+__attribute__ ((visibility ("default")))
+int openssl_verify_data(const keymaster_device_t*,
         const void* params,
         const uint8_t* keyBlob, const size_t keyBlobLength,
         const uint8_t* signedData, const size_t signedDataLength,
@@ -728,7 +723,11 @@
     }
 
     int type = EVP_PKEY_type(pkey->type);
-    if (type == EVP_PKEY_RSA) {
+    if (type == EVP_PKEY_DSA) {
+        keymaster_dsa_sign_params_t* sign_params = (keymaster_dsa_sign_params_t*) params;
+        return verify_dsa(pkey.get(), sign_params, signedData, signedDataLength, signature,
+                signatureLength);
+    } else if (type == EVP_PKEY_RSA) {
         keymaster_rsa_sign_params_t* sign_params = (keymaster_rsa_sign_params_t*) params;
         return verify_rsa(pkey.get(), sign_params, signedData, signedDataLength, signature,
                 signatureLength);
@@ -741,63 +740,3 @@
         return -1;
     }
 }
-
-/* Close an opened OpenSSL instance */
-static int openssl_close(hw_device_t *dev) {
-    delete dev;
-    return 0;
-}
-
-/*
- * Generic device handling
- */
-static int openssl_open(const hw_module_t* module, const char* name,
-        hw_device_t** device) {
-    if (strcmp(name, KEYSTORE_KEYMASTER) != 0)
-        return -EINVAL;
-
-    Unique_keymaster_device_t dev(new keymaster_device_t);
-    if (dev.get() == NULL)
-        return -ENOMEM;
-
-    dev->common.tag = HARDWARE_DEVICE_TAG;
-    dev->common.version = 1;
-    dev->common.module = (struct hw_module_t*) module;
-    dev->common.close = openssl_close;
-
-    dev->flags = KEYMASTER_SOFTWARE_ONLY;
-
-    dev->generate_keypair = openssl_generate_keypair;
-    dev->import_keypair = openssl_import_keypair;
-    dev->get_keypair_public = openssl_get_keypair_public;
-    dev->delete_keypair = NULL;
-    dev->delete_all = NULL;
-    dev->sign_data = openssl_sign_data;
-    dev->verify_data = openssl_verify_data;
-
-    ERR_load_crypto_strings();
-    ERR_load_BIO_strings();
-
-    *device = reinterpret_cast<hw_device_t*>(dev.release());
-
-    return 0;
-}
-
-static struct hw_module_methods_t keystore_module_methods = {
-    open: openssl_open,
-};
-
-struct keystore_module HAL_MODULE_INFO_SYM
-__attribute__ ((visibility ("default"))) = {
-    common: {
-        tag: HARDWARE_MODULE_TAG,
-        version_major: 1,
-        version_minor: 0,
-        id: KEYSTORE_HARDWARE_MODULE_ID,
-        name: "Keymaster OpenSSL HAL",
-        author: "The Android Open Source Project",
-        methods: &keystore_module_methods,
-        dso: 0,
-        reserved: {},
-    },
-};
diff --git a/softkeymaster/module.cpp b/softkeymaster/module.cpp
new file mode 100644
index 0000000..758dfe7
--- /dev/null
+++ b/softkeymaster/module.cpp
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <errno.h>
+#include <string.h>
+#include <stdint.h>
+
+#include <keymaster/softkeymaster.h>
+
+#include <keystore/keystore.h>
+
+#include <hardware/hardware.h>
+#include <hardware/keymaster.h>
+
+#include <openssl/err.h>
+
+#include <utils/UniquePtr.h>
+
+// For debugging
+//#define LOG_NDEBUG 0
+
+#define LOG_TAG "OpenSSLKeyMaster"
+#include <cutils/log.h>
+
+typedef UniquePtr<keymaster_device_t> Unique_keymaster_device_t;
+
+/* Close an opened OpenSSL instance */
+static int openssl_close(hw_device_t *dev) {
+    delete dev;
+    return 0;
+}
+
+/*
+ * Generic device handling
+ */
+static int openssl_open(const hw_module_t* module, const char* name,
+        hw_device_t** device) {
+    if (strcmp(name, KEYSTORE_KEYMASTER) != 0)
+        return -EINVAL;
+
+    Unique_keymaster_device_t dev(new keymaster_device_t);
+    if (dev.get() == NULL)
+        return -ENOMEM;
+
+    dev->common.tag = HARDWARE_DEVICE_TAG;
+    dev->common.version = 1;
+    dev->common.module = (struct hw_module_t*) module;
+    dev->common.close = openssl_close;
+
+    dev->flags = KEYMASTER_SOFTWARE_ONLY;
+
+    dev->generate_keypair = openssl_generate_keypair;
+    dev->import_keypair = openssl_import_keypair;
+    dev->get_keypair_public = openssl_get_keypair_public;
+    dev->delete_keypair = NULL;
+    dev->delete_all = NULL;
+    dev->sign_data = openssl_sign_data;
+    dev->verify_data = openssl_verify_data;
+
+    ERR_load_crypto_strings();
+    ERR_load_BIO_strings();
+
+    *device = reinterpret_cast<hw_device_t*>(dev.release());
+
+    return 0;
+}
+
+static struct hw_module_methods_t keystore_module_methods = {
+    open: openssl_open,
+};
+
+struct keystore_module HAL_MODULE_INFO_SYM
+__attribute__ ((visibility ("default"))) = {
+    common: {
+        tag: HARDWARE_MODULE_TAG,
+        module_api_version: KEYMASTER_MODULE_API_VERSION_0_2,
+        hal_api_version: HARDWARE_HAL_API_VERSION,
+        id: KEYSTORE_HARDWARE_MODULE_ID,
+        name: "Keymaster OpenSSL HAL",
+        author: "The Android Open Source Project",
+        methods: &keystore_module_methods,
+        dso: 0,
+        reserved: {},
+    },
+};