单向函数、单向陷门函数、困难问题

1、单向函数

设函数 y=f(x) ，

• 对于给定的x，计算出y很容易；
• 对于给定的y，计算出x很难。

2、单向陷门函数

设函数 y=f(x) ，且f有陷门，

• 对于给定的x，计算出y很容易；
• 对于给定的y，在不掌握陷门的情况下，计算出x很难；而若在掌握陷门的情况下，计算出x很容易。

3、已找到的单向性足够的函数（困难问题） 

• 大整数的因数分解问题‌：给定两个大素数 p 和 q ，计算它们的乘积 是容易的，但给定 n 求 p 和 q （）是非常困难的。应用例子如：RSA算法。
• 有限域上的‌离散对数问题‌(DLP)：在有限域中，大素数的幂乘（）容易计算，而对数（）计算困难。应用例子如：Diffie-Hellman密钥交换协议。‌