diff --git a/bindep.txt b/bindep.txt
index 8d8c45b..b34b158 100644
--- a/bindep.txt
+++ b/bindep.txt
@@ -5,3 +5,11 @@
 mysql-server [test]
 libjpeg-dev [test]
 zookeeperd [platform:dpkg]
+build-essential [platform:dpkg]
+gcc [platform:rpm]
+libssl-dev [platform:dpkg]
+openssl-devel [platform:rpm]
+libffi-dev [platform:dpkg]
+libffi-devel [platform:rpm]
+python-dev [platform:dpkg]
+python-devel [platform:rpm]
diff --git a/requirements.txt b/requirements.txt
index 186e7f6..c7e059a 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -19,3 +19,4 @@
 kazoo
 sqlalchemy
 alembic
+cryptography>=1.6
diff --git a/tests/base.py b/tests/base.py
index 2729233..b039267 100755
--- a/tests/base.py
+++ b/tests/base.py
@@ -50,6 +50,7 @@
 import testtools.content
 import testtools.content_type
 from git.exc import NoSuchPathError
+import yaml
 
 import zuul.driver.gerrit.gerritsource as gerritsource
 import zuul.driver.gerrit.gerritconnection as gerritconnection
@@ -1209,6 +1210,11 @@
         different tenant/project layout while using the standard main
         configuration.
 
+    :cvar bool create_project_keys: Indicates whether Zuul should
+        auto-generate keys for each project, or whether the test
+        infrastructure should insert dummy keys to save time during
+        startup.  Defaults to False.
+
     The following are instance variables that are useful within test
     methods:
 
@@ -1240,6 +1246,7 @@
 
     config_file = 'zuul.conf'
     run_ansible = False
+    create_project_keys = False
 
     def _startMerger(self):
         self.merge_server = zuul.merger.server.MergeServer(self.config,
@@ -1434,6 +1441,39 @@
                     project = reponame.replace('_', '/')
                     self.copyDirToRepo(project,
                                        os.path.join(git_path, reponame))
+        self.setupAllProjectKeys()
+
+    def setupAllProjectKeys(self):
+        if self.create_project_keys:
+            return
+
+        path = self.config.get('zuul', 'tenant_config')
+        with open(os.path.join(FIXTURE_DIR, path)) as f:
+            tenant_config = yaml.safe_load(f.read())
+        for tenant in tenant_config:
+            sources = tenant['tenant']['source']
+            for source, conf in sources.items():
+                for project in conf.get('config-repos', []):
+                    self.setupProjectKeys(source, project)
+                for project in conf.get('project-repos', []):
+                    self.setupProjectKeys(source, project)
+
+    def setupProjectKeys(self, source, project):
+        # Make sure we set up an RSA key for the project so that we
+        # don't spend time generating one:
+
+        key_root = os.path.join(self.state_root, 'keys')
+        if not os.path.isdir(key_root):
+            os.mkdir(key_root, 0o700)
+        private_key_file = os.path.join(key_root, source, project + '.pem')
+        private_key_dir = os.path.dirname(private_key_file)
+        self.log.debug("Installing test keys for project %s at %s" % (
+            project, private_key_file))
+        if not os.path.isdir(private_key_dir):
+            os.makedirs(private_key_dir)
+        with open(os.path.join(FIXTURE_DIR, 'private.pem')) as i:
+            with open(private_key_file, 'w') as o:
+                o.write(i.read())
 
     def setupZK(self):
         self.zk_chroot_fixture = self.useFixture(ChrootedKazooFixture())
@@ -1469,6 +1509,22 @@
             self.assertFalse(node['_lock'], "Node %s is locked" %
                              (node['_oid'],))
 
+    def assertNoGeneratedKeys(self):
+        # Make sure that Zuul did not generate any project keys
+        # (unless it was supposed to).
+
+        if self.create_project_keys:
+            return
+
+        with open(os.path.join(FIXTURE_DIR, 'private.pem')) as i:
+            test_key = i.read()
+
+        key_root = os.path.join(self.state_root, 'keys')
+        for root, dirname, files in os.walk(key_root):
+            for fn in files:
+                with open(os.path.join(root, fn)) as f:
+                    self.assertEqual(test_key, f.read())
+
     def assertFinalState(self):
         # Make sure that git.Repo objects have been garbage collected.
         repos = []
@@ -1480,6 +1536,7 @@
         self.assertEqual(len(repos), 0)
         self.assertEmptyQueues()
         self.assertNodepoolState()
+        self.assertNoGeneratedKeys()
         ipm = zuul.manager.independent.IndependentPipelineManager
         for tenant in self.sched.abide.tenants.values():
             for pipeline in tenant.layout.pipelines.values():
@@ -1846,6 +1903,7 @@
         f.close()
         self.config.set('zuul', 'tenant_config',
                         os.path.join(FIXTURE_DIR, f.name))
+        self.setupAllProjectKeys()
 
     def addCommitToRepo(self, project, message, files,
                         branch='master', tag=None):
diff --git a/tests/fixtures/private.pem b/tests/fixtures/private.pem
new file mode 100644
index 0000000..fa709b6
--- /dev/null
+++ b/tests/fixtures/private.pem
@@ -0,0 +1,51 @@
+-----BEGIN RSA PRIVATE KEY-----
+MIIJKgIBAAKCAgEAsGqZLUUwV/EZJKddMS206mH7qYmqYhWLo/TUlpDt2JuEaBqC
+YV8mF9LsjpoqM/Pp0U/r5aQLDUXbRLDn+K+NqbvTJajYxHJicP1CAWg1eKUNZjUa
+ya5HP4Ow1hS7AeiF4TSRdiwtHT/gJO2NSsavyc30/meKt0WBgbYlrBB81HEQjYWn
+ajf/4so5E8DdrC9tAqmmzde1qcTz7ULouIz53hjp/U3yVMFbpawv194jzHvddmAX
+3aEUByx2t6lP7dhOAEIEmzmh15hRbacxQI5aYWv+ZR0z9PqdwwD+DBbb1AwiX5MJ
+jtIoVCmkEZvcUFiDicyteNMCa5ulpj2SF0oH4MlialOP6MiJnmxklDYO07AM/qom
+cU55pCD8ctu1yD/UydecLk0Uj/9XxqmPQJFEcstdXJZQfr5ZNnChOEg6oQ9UImWj
+av8HQsA6mFW1oAKbDMrgEewooWriqGW5pYtR7JBfph6Mt5HGaeH4uqYpb1fveHG1
+ODa7HBnlNo3qMendBb2wzHGCgtUgWnGfp24TsUOUlndCXYhsYbOZbCTW5GwElK0G
+ri06KPpybY43AIaxcxqilVh5Eapmq7axBm4ZzbTOfv15L0FIemEGgpnklevQbZNL
+IrcE0cS/13qJUvFaYX4yjrtEnzZ3ntjXrpFdgLPBKn7Aqf6lWz6BPi07axECAwEA
+AQKCAgEAkoPltYhZ7x+ojx2Es1xPfb1kwlg4Ln/QWpnymR3Cu3vlioRBtlbMj0q4
+9nIpDL7NeO4Ub8M+/oX+5ly6O3qpf8cjRIqnhPeutEJRuFNw3ULPDwyZs9hPCfv4
+OMQ80AfqcLA1At0Lltg+8sxr5SeARW0MxOD/fth2B2FchjunQNSqN69B7GCX3yWu
+I66xK9izg1uc0iYNlPKi13ETUHqc5ozwgFRlJ2jzEXQgw/qU5rYUpsSF7aZiuNZ/
+vmcan+FeXq51nulNdX3mWthZelD/1RtYy2dmiFZAAf1oAGhXqBNv1MqMTJZTshpn
+TcyRPBVXIXHgvJEa2H4LJDbMhxUP1opJ+Vxa8Cy6I60O8TwPBHwL83K5oH4yugun
+AP2hWZxFMK9YcVliJwt3Mjozuh5vCRF9+7oqi0fASuhOY+eYNQAtcPK9WBti6qmN
+hUO4bdx+r+UEb8TliUDH+x5lNmKc2pgptYS+O8+oB2vh2V7e0mwvc3jg4S7E5Ukm
+y4Y9JS0c4q352W0lrfPCDYwzXEpK8mmCjvBC/w320Yi2HJwqkfYQThgEbzOP37dW
+Ei+0+cu6RuA4H+1DozkrWybFw6Ju12IE4vfbliyht1yuj0+/Rpevp1KpFKuy5xSB
+1Jq3lGxTFDGle7nRBc2JwfIu63texnmvTwKlx1+w0tqpY/gVZhUCggEBAOAzVHum
+luqKVewWT8yR4mZx4jiWdxLch3Q+scMq2mthQ5773Of0P2r45iJz7jDS7fT0yuRF
+gBpqygX42xe+wqJleKAzKyMQ9aWtYRszfCz6Ob9kLTtoi0/Xuo5dMyg41BRHAatr
+acj9NXBEvRS4oNKw3nxEVayBjvYN5LwLAzGNorXCkt9E+72eWJU6eg0CQQxwI2rG
+f/S+niMtLDWfayHPu7KBKRVlUu1kI07JF1eSJmsHBcTN1+CaXuN82Ty+ucdtjRWR
+5FyLZxaceLGrY5so87pH7kcBB2+H7ovuash7g+CT3XyDcQACWTjTszIpt6fGO6ux
+7Tea5/OOLaJiaI8CggEBAMlwPPW3HQzC6dqwBVNgVYQh9ZEoygKOWNMPNE1TuqUU
+boJLazQI5Qd/qm17otAnDrIX7cEB/+6xiQPZkw6lsqdzGHNBSXb8OPYvLDBHq2oR
+oNjdW4/c5znBL3ExXqEJIHAl9FWc5YLRvboHwtkKCpK5mdlZyoMVsBX62IFodAhK
+a8oQiLvYjOwFOay3sOMdhc+ndupw7b9MaAsbe1w7DW3Y7I/bHstxiriDfuTI/nt7
+MPZBzj9afqWHEJ3TWwuJ1IuUhHupf9ylA06GfBgerWSlp90yVfbZNQDljtdNwIZW
+oBLF6EhZxh6ka8iodeS4cduxEV3BoofMXjIjVReCgl8CggEBALSwabwl7Kclyk21
+RabnRAGwctOMYHbxCLHk/Tr/xHyaLPdqoQTH0nySEFdf+22Z8XFkAEiswquHuT3K
+7Dhc41wiT289Ddz7BB78drCHc+KD4Bqhz9p7TRuSD6ZA8sPN2Q5mk6/lp6H2gCT1
+ITYb/nEPXp/kKvAWknM3i0sJzQ8YyTOXluseG40cmuPZ9xeY43f0wHaDeAh1v9k1
+xNWKn7rmQq2Abu3xdT4hYFtUsd0/ynqjdEDCbON1Rlgs/J96Txus7PGfXN5A81pD
+zPnT2TjpblSJOD49VBLNCLH5+lGNSiGqyexZuq55NhMYeulIud0bZGfhw/72d03R
+HnIqwX0CggEBAKiKglbMuT+eLfBN6obSSXretwqXaD4vP96IECjK75WDvNrDo5TM
+BGT7ymsEUTt8Em2sW79rnunmHU/dUY+l0A8O29xDOeaWLkq9OWnD7YY37a7FtwBt
+wgGuw7Ufq59tdXigKQkg119XgjkOmVbjcelF5ZXX7Ps0wDoDwfa0oLD3I6zTnLQf
+AfnQfWsn3paIcxdFdNe/WQ0ALuVsPxDyT9Ai+ft7SQ7Ll1e+ngNqsJI8hsDkWl7j
+pqd0lNCYsMq8rduDjj2xmkvQvS2MlHPR5x4ZBJSsswRwxEpVx+gZJAbCn/hVIn62
+rm+g/pXLbajLMmiwhGk/xG9+7SliKqYbCl0CggEATQtwqAVPdwzT5XaRS1CeLId5
+sZD8mP5WLBKas69nfISilcUKqJjqTTqxfXs60wOK3/r43B+7QLitfPLRqf0hRQT9
+6HQG1YGx1FfZwgsP5SJKpAGGjenhsSTwpMJJI5s2I2e1O01frF2qEodqmRUwHXbh
+rGXqzAHLieaBzHjSvS2Z4kGVu6ZbpRXSNTSiiF+z8O9PCahzNFrC/ty+lbtxcqhf
+wHttEccW1TmiuB9GD23NI96zLsjZALvdqpvHMf5OHiDdLmI+Ap7qlR04V3bDDzF4
+B6HR6bRxVZQQWaEwE1RfuDgj5Msrbcgq0yFayPvXGiIIrAUWkUUQVsUU/TOfBQ==
+-----END RSA PRIVATE KEY-----
diff --git a/tests/unit/test_v3.py b/tests/unit/test_v3.py
index 5c0679d..52b4177 100644
--- a/tests/unit/test_v3.py
+++ b/tests/unit/test_v3.py
@@ -17,10 +17,12 @@
 import os
 import textwrap
 
+from cryptography.hazmat.primitives import serialization
+from cryptography.hazmat.backends import default_backend
 import testtools
 
 import zuul.configloader
-from tests.base import AnsibleZuulTestCase, ZuulTestCase
+from tests.base import AnsibleZuulTestCase, ZuulTestCase, FIXTURE_DIR
 
 
 class TestMultipleTenants(AnsibleZuulTestCase):
@@ -303,3 +305,36 @@
 
     def test_broken_config_on_startup(self):
         pass
+
+
+class TestProjectKeys(ZuulTestCase):
+    # Test that we can generate project keys
+
+    # Normally the test infrastructure copies a static key in place
+    # for each project before starting tests.  This saves time because
+    # Zuul's automatic key-generation on startup can be slow.  To make
+    # sure we exercise that code, in this test we allow Zuul to create
+    # keys for the project on startup.
+    create_project_keys = True
+    tenant_config_file = 'config/in-repo/main.yaml'
+
+    def test_key_generation(self):
+        key_root = os.path.join(self.state_root, 'keys')
+        private_key_file = os.path.join(key_root, 'gerrit/org/project.pem')
+        # Make sure that a proper key was created on startup
+        with open(private_key_file, "rb") as f:
+            private_key = serialization.load_pem_private_key(
+                f.read(),
+                password=None,
+                backend=default_backend()
+            )
+
+        with open(os.path.join(FIXTURE_DIR, 'private.pem')) as i:
+            fixture_private_key = i.read()
+
+        # Make sure that we didn't just end up with the static fixture
+        # key
+        self.assertNotEqual(fixture_private_key, private_key)
+
+        # Make sure it's the right length
+        self.assertEqual(4096, private_key.key_size)
diff --git a/zuul/configloader.py b/zuul/configloader.py
index 8bae3c5..8439fc3 100644
--- a/zuul/configloader.py
+++ b/zuul/configloader.py
@@ -21,6 +21,9 @@
 
 import voluptuous as vs
 
+from cryptography.hazmat.backends import default_backend
+from cryptography.hazmat.primitives.asymmetric import rsa
+from cryptography.hazmat.primitives import serialization
 from zuul import model
 import zuul.manager.dependent
 import zuul.manager.independent
@@ -465,6 +468,7 @@
                 project_pipeline.queue_name = queue_name
             if pipeline_defined:
                 project.pipelines[pipeline.name] = project_pipeline
+
         return project
 
 
@@ -673,13 +677,15 @@
         return vs.Schema(tenant)
 
     @staticmethod
-    def fromYaml(base, connections, scheduler, merger, conf, cached):
+    def fromYaml(base, project_key_dir, connections, scheduler, merger, conf,
+                 cached):
         TenantParser.getSchema(connections)(conf)
         tenant = model.Tenant(conf['name'])
         tenant.unparsed_config = conf
         unparsed_config = model.UnparsedTenantConfig()
         tenant.config_repos, tenant.project_repos = \
-            TenantParser._loadTenantConfigRepos(connections, conf)
+            TenantParser._loadTenantConfigRepos(
+                project_key_dir, connections, conf)
         for source, repo in tenant.config_repos:
             tenant.addConfigRepo(source, repo)
         for source, repo in tenant.project_repos:
@@ -699,7 +705,70 @@
         return tenant
 
     @staticmethod
-    def _loadTenantConfigRepos(connections, conf_tenant):
+    def _loadProjectKeys(project_key_dir, connection_name, project):
+        project.private_key_file = (
+            os.path.join(project_key_dir, connection_name,
+                         project.name + '.pem'))
+
+        TenantParser._generateKeys(project)
+        TenantParser._loadKeys(project)
+
+    @staticmethod
+    def _generateKeys(project):
+        if os.path.isfile(project.private_key_file):
+            return
+
+        key_dir = os.path.dirname(project.private_key_file)
+        if not os.path.isdir(key_dir):
+            os.makedirs(key_dir)
+
+        TenantParser.log.info(
+            "Generating RSA keypair for project %s" % (project.name,)
+        )
+
+        # Generate private RSA key
+        private_key = rsa.generate_private_key(
+            public_exponent=65537,
+            key_size=4096,
+            backend=default_backend()
+        )
+        # Serialize private key
+        pem_private_key = private_key.private_bytes(
+            encoding=serialization.Encoding.PEM,
+            format=serialization.PrivateFormat.TraditionalOpenSSL,
+            encryption_algorithm=serialization.NoEncryption()
+        )
+
+        TenantParser.log.info(
+            "Saving RSA keypair for project %s to %s" % (
+                project.name, project.private_key_file)
+        )
+
+        # Dump keys to filesystem
+        with open(project.private_key_file, 'wb') as f:
+            f.write(pem_private_key)
+
+    @staticmethod
+    def _loadKeys(project):
+        # Check the key files specified are there
+        if not os.path.isfile(project.private_key_file):
+            raise Exception(
+                'Private key file {0} not found'.format(
+                    project.private_key_file))
+
+        # Load private key
+        with open(project.private_key_file, "rb") as f:
+            project.private_key = serialization.load_pem_private_key(
+                f.read(),
+                password=None,
+                backend=default_backend()
+            )
+
+        # Extract public key from private
+        project.public_key = project.private_key.public_key()
+
+    @staticmethod
+    def _loadTenantConfigRepos(project_key_dir, connections, conf_tenant):
         config_repos = []
         project_repos = []
 
@@ -708,10 +777,14 @@
 
             for conf_repo in conf_source.get('config-repos', []):
                 project = source.getProject(conf_repo)
+                TenantParser._loadProjectKeys(
+                    project_key_dir, source_name, project)
                 config_repos.append((source, project))
 
             for conf_repo in conf_source.get('project-repos', []):
                 project = source.getProject(conf_repo)
+                TenantParser._loadProjectKeys(
+                    project_key_dir, source_name, project)
                 project_repos.append((source, project))
 
         return config_repos, project_repos
@@ -861,7 +934,8 @@
                             config_path)
         return config_path
 
-    def loadConfig(self, config_path, scheduler, merger, connections):
+    def loadConfig(self, config_path, project_key_dir, scheduler, merger,
+                   connections):
         abide = model.Abide()
 
         config_path = self.expandConfigPath(config_path)
@@ -874,13 +948,14 @@
 
         for conf_tenant in config.tenants:
             # When performing a full reload, do not use cached data.
-            tenant = TenantParser.fromYaml(base, connections, scheduler,
-                                           merger, conf_tenant, cached=False)
+            tenant = TenantParser.fromYaml(
+                base, project_key_dir, connections, scheduler, merger,
+                conf_tenant, cached=False)
             abide.tenants[tenant.name] = tenant
         return abide
 
-    def reloadTenant(self, config_path, scheduler, merger, connections,
-                     abide, tenant):
+    def reloadTenant(self, config_path, project_key_dir, scheduler,
+                     merger, connections, abide, tenant):
         new_abide = model.Abide()
         new_abide.tenants = abide.tenants.copy()
 
@@ -888,9 +963,9 @@
         base = os.path.dirname(os.path.realpath(config_path))
 
         # When reloading a tenant only, use cached data if available.
-        new_tenant = TenantParser.fromYaml(base, connections, scheduler,
-                                           merger, tenant.unparsed_config,
-                                           cached=True)
+        new_tenant = TenantParser.fromYaml(
+            base, project_key_dir, connections, scheduler, merger,
+            tenant.unparsed_config, cached=True)
         new_abide.tenants[tenant.name] = new_tenant
         return new_abide
 
diff --git a/zuul/model.py b/zuul/model.py
index 3676b68..9c395c4 100644
--- a/zuul/model.py
+++ b/zuul/model.py
@@ -2084,6 +2084,7 @@
         self.name = name
         self.merge_mode = None
         self.pipelines = {}
+        self.private_key_file = None
 
 
 class UnparsedAbideConfig(object):
diff --git a/zuul/scheduler.py b/zuul/scheduler.py
index 7fb1568..6ae8492 100644
--- a/zuul/scheduler.py
+++ b/zuul/scheduler.py
@@ -452,6 +452,22 @@
             os.mkdir(d)
         return d
 
+    def _get_project_key_dir(self):
+        if self.config.has_option('zuul', 'state_dir'):
+            state_dir = os.path.expanduser(self.config.get('zuul',
+                                                           'state_dir'))
+        else:
+            state_dir = '/var/lib/zuul'
+        key_dir = os.path.join(state_dir, 'keys')
+        if not os.path.exists(key_dir):
+            os.mkdir(key_dir, 0o700)
+        st = os.stat(key_dir)
+        mode = st.st_mode & 0o777
+        if mode != 0o700:
+            raise Exception("Project key directory %s must be mode 0700; "
+                            "current mode is %o" % (key_dir, mode))
+        return key_dir
+
     def _save_queue(self):
         pickle_file = self._get_queue_pickle_file()
         events = []
@@ -507,6 +523,7 @@
             loader = configloader.ConfigLoader()
             abide = loader.loadConfig(
                 self.config.get('zuul', 'tenant_config'),
+                self._get_project_key_dir(),
                 self, self.merger, self.connections)
             for tenant in abide.tenants.values():
                 self._reconfigureTenant(tenant)
@@ -523,6 +540,7 @@
             loader = configloader.ConfigLoader()
             abide = loader.reloadTenant(
                 self.config.get('zuul', 'tenant_config'),
+                self._get_project_key_dir(),
                 self, self.merger, self.connections,
                 self.abide, event.tenant)
             tenant = abide.tenants[event.tenant.name]