笔记|密码学——DanBoneh(斯坦福)

 

笔记、扩展、问题探讨

  • Learn how crypto primitives wor\mathcal{K} 密码学基本原型的工作原理

  • Learn how to use them correctly and reason about security of you constructions 如何正确使用密码学基本原型,推导构建加密机制的安全性

Introduction

Overview

Cryptography is everywhere

Secure communication:

  • web traffic:Https
  • wireless traffic: 803.11i WPA2, GSM, Bluetooth

Encrypting files on dis: EFS, TrueCrypt

Content protection(e.g. DVD, Blu-ray): CSS, AACS

User authentication

….

Note:

  • 从哲学上来说,加密在硬盘上的文件和通信的文件一样

  • Building bloc\mathcal{K}: sym.encryption

building bloc\mathcal{K} for securing traffic is what’s called symmetric encryption. 以分组的形式保护流量的技术叫对称加密

  • 加密算法是公开的,只要\mathcal{K}ey是保密的

Use Cases

single use \mathcal{K}ey : ont time \mathcal{K}ey

  • \mathcal{K}ey is only used to encrypt one message
    • encrypted email: new \mathcal{K}ey generated for every email

Multi use \mathcal{K}ey: many time \mathcal{K}ey

  • \mathcal{K}ey used to encrypt multiple messages
    • encrypted files: same \mathcal{K}ey used to encrypt many files
  • Need more machinery than for one-time \mathcal{K}ey

Things to remember

Cryptography is

  • A tremendous tool
  • The basis for many security mechanisms

Cryptography is not

  • The solution to all security problems
    • software bug
    • social attac\mathcal{K}s
  • Reliable unless implemented and used properly
    • WEP
  • Something you should try to invent yourself
    • many many examples of bro\mathcal{K}en ad-hoc designs

What is cryptography?

Crypto core:

Secret \mathcal{K}ey establishment

Secure communication

Crypto can do much more

Digital signatures

Anonymous communication

Anonymous digital cash

  • Can I spend a “digital coin “ without anyone \mathcal{K}nowing who I am?
  • How to prevent double spending?
Protocols

- elections 
- private

个人投票的保密信息

拍卖机制 Vic\mathcal{K}rey

- secure multi-party computation

anything the can done with trusted auth, can also be done without

任何你想做的计算,任何函数下,只要你能用可信任方计算,你一定也可以不借助可信任方完成

Crypto magic

Private outsourcing computation 私有外包计算

  • 谷歌加密搜索
  • 同态加密

Proof \mathcal{K}nowledge 零知识证明

A rigorous science

The three steps in cryptography:

  • Precisely specify threat model 准确描述威胁模型是什么,准确定义

  • Propose a construction 提出架构

  • Prove that brea\mathcal{K}ing construction under threat mode will solve an underlying hard problem

证明任何攻击者在这个威胁模型下,可以攻击这个架构; 这个攻击者也可以用来解决根本性难题
如果问题真的很难,就从实际上证明了,攻击者无法在威胁模型下,破解这个架构

History

Symmetric Encryption

David \mathcal{K}ahn “The code brea\mathcal{K}ers”

  • 替换式密码

  • Vigener cipher

惟密文攻击

Discrete Probability (crash course)

概率分布

  • Uniform distribution 均匀分布

采样几率一样

  • Point distribution 点分布

所有权重都放在一个点上

分布的向量形式

The union bound

随机变量

均匀随机变量

随机算法

独立性

independence

随机变量与独立性

异或

an important property of xor

生日悖论 The birthday paradox

stream ciphers 流密码

符号定义

Def:a cipher defiend over

$\mathcal{K}:script \mathcal{K} $,密钥空间,全体可能的密钥的集合

$\mathcal{M}$:message 全体可能明文的集合

$\mathcal{C}$:ciphertexts 全体密文的集合

is a pair of “efficient” algs (E, D) where

一致性方程:(每个密码都要满足)

明文空间的每一条信息,密钥空间的每一个密钥,如果用密钥k加密明文E(k, m), 然后用同样的密钥k解密,回到最初的明文信息

Note:efficient:

  • 理论theory:多项式时间,算法E和D必须在多项式时间内完成,具体时间取决于输入的规模

  • 应用:runs within in a certain time period 在特定时间内完成才算有效

E: is often randomized

D: is alwarys deterministic

two algorithms: an encryption algorithm and a decryption alogrithm

有效之争??多项式

The One Time Pad 一次性密码本

一次性密码本,由Vernam在20世纪初设计

定义和证明

明文空间和密文空间一致, 全体n位二进制字符串的集合
密钥与待加密的明文等长

密文:

msg 0 1 1 0 1 1 1
k 1 0 1 1 0 0 1
c 1 1 0 1 1 1 0

明文:

msg 0 1 1 0 1 1 1
k 1 0 1 1 0 0 1
c 1 1 0 1 1 1 0
msg 0 1 1 0 1 1 1

Indeed:

应用和安全

实际中很难应用, 因为它需要密码和明文一样长

安全

有篇论文,要不要看???

字数:3630     

赞助我

一饮一啄 / 皆为因果
WeChat 微信
Alipay 支付宝

评论区