Cipher Requirements and Trapdoor One-Way Function

Loading...

Do curso por University of Colorado System

Asymmetric Cryptography and Key Management

29 ratings

University of Colorado System

Asymmetric Cryptography and Key Management

29 ratings

Curso 3 de 4 em Specialization Applied Cryptography

Welcome to Asymmetric Cryptography and Key Management! In asymmetric cryptography or public-key cryptography, the sender and the receiver use a pair of public-private keys, as opposed to the same symmetric key, and therefore their cryptographic operations are asymmetric. This course will first review the principles of asymmetric cryptography and describe how the use of the pair of keys can provide different security properties. Then, we will study the popular asymmetric schemes in the RSA cipher algorithm and the Diffie-Hellman Key Exchange protocol and learn how and why they work to secure communications/access. Lastly, we will discuss the key distribution and management for both symmetric keys and public keys and describe the important concepts in public-key distribution such as public-key authority, digital certificate, and public-key infrastructure. This course also describes some mathematical concepts, e.g., prime factorization and discrete logarithm, which become the bases for the security of asymmetric primitives, and working knowledge of discrete mathematics will be helpful for taking this course; the Symmetric Cryptography course (recommended to be taken before this course) also discusses modulo arithmetic. This course is cross-listed and is a part of the two specializations, the Applied Cryptography specialization and the Introduction to Applied Cryptography specialization.

Na lição

Asymmetric Cryptography Overview

This module reviews the principles and requirements of asymmetric cryptography, which uses a pair of keys - with one party using a public key and the other using the corresponding private key or vice versa - in contrast to symmetric cryptography using a shared secret key.

Cipher Requirements and Trapdoor One-Way Function4:46

Conheça os instrutores

Sang-Yoon Chang
Assistant Professor
Computer Science

We previously discussed about how to use the keys and

how they affect the security applications of asymmetric cryptography.

For example, next to me is the diagram we use for digital signature.

Now let's shift gears and focus our attention to

the requirements of the cipher algorithms which corresponds to

the encryption and decryption functions and the public private key pair.

To be used for asymmetric cryptography,

the cipher and the key pair needs to fulfill the following requirements.

First, it should be computationally easy for any user I to generate a pair of

public key and private key so that

the decryption using one key reverses the encryption using the other key.

Generally, computationally easy is defined to mean a problem that

can be solved in polynomial time as a function of the input length.

Second, if holding the correct keys,

the encryption operation and the decryption processing are computationally easy.

In other words, Alice's computation for encryption and Bob's computation

for decryption should be computationally efficient.

Shifting our focus to the attacker's perspective,

the third requirement for the cipher is that it should be computationally

infeasible for an attacker knowing the public key to determine the private key.

Otherwise, the attacker will easily compromise

the private key after accessing the public key.

Fourth, it should be computationally infeasible for an attacker knowing

the public key K and a ciphertext C to recover the original plaintext P. In other words,

the attacker knowing the ciphertext from a public key cannot derive the plaintext.

An optional requirement for the cipher design is to support broader applications.

And the optional requirement is that the two keys can be applied in

either order so that for any plaintext PST input,

the decryption with the public key reverses the encryption with the private key.

And the decryption with the private key reverses the encryption with the public key.

These requirements can be challenging to meet and there are

only a few algorithms that are widely accepted for asymmetric cryptography such as RSA,

Elliptic Curve Crypro, Diffie-Hellman key exchange and DSS.

And this is even though it has been decades since

the concept of public key cryptography was proposed in the 1970s.

The cipher requirements boil down to the need for a trapdoor one-way function.

A one-way function is a function where the calculation of the function is computationally

easy while the calculation of the inverse is computationally infeasible.

That is, it is easy to compute in one direction from the input to the output,

but it is difficult to reverse that and determine the input from the output.

A trapdoor one-way function is a one-way function with more conditions.

A trapdoor one-way function is easy to calculate in one direction and infeasible

to calculate in the other direction unless certain additional information is known.

With the additional information,

the inverse can be calculated in polynomial time.

In other words, it's easy to compute with the additional information.

In other words, given that K is

the additional information or the key that makes the computation easy,

a trapdoor one-way function is a family of invertible functions F sub K such

that the computation for Y equals F sub K of X is easy if K and X are known.

The computation for X equals the inverse of F sub K of Y is easy if K and Y are known.

Third, the computation for X equals F sub K,

the inverse of F sub K of Y is infeasible if Y is known but K is not known.

Such trapdoor one-way function plays a significant role in asymmetric cryptography.

And the development of

a practical asymmetric cryptography scheme

depends on the discovery of a suitable trap door one-way function.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play