coperlm's Blog

之前很早就听机房的学长说主定理了，是用于算法竞赛中分析时间复杂度的，但是一直没有学习过 今天做DS，又遇到了，题目如下 一道考研题目 解析：时间复杂度为 $O(nlogn)$ 设 $n=2^k(k\geq0)$，有 $T(2^k)=2T(2^{k-1})+2^k=2^2T(2^{k-2})+2*2^k$ 由此得到递推公式 $T(2^k)=2^iT(2^{k-i})+i*2^k$ 故 $T(2^k)=2^kT(2^0)+k*2^k=(k+1)2^k$ 带回 $n$ 得到 $T(n)=(logn+1)2^{logn}$ 即时间复杂度为 $O(nlogn)$ 这也就是归并排序(MergeSort)的时间复杂度 更普适的假设有递推关系式 $T(n)=aT(\frac{n}{b})+f(n)$，其中$a\ge1,b>1$ 其中，$n$ 为问题规模，$a$ 为递归的子问题数量，$\frac{n}{b}$ 为每个子问题的规模（假设每个子问题的规模基本一样），$f(n)$...

三道挺有意思的小题目，记录一下 第一题题目描述：说反话 题解： 翻转字符串即可（大雾），时间复杂度是严格线性（大大雾） 第二题题目描述：挑战者选择16/17/18张卡片和先/后手，每方每次可以掀开1/2/3张卡片；挑战者的目标是让敌手掀开最后一张卡牌 题解： 如果敌手掀开最后一张牌（即达成挑战目标），则必然最终只剩一张牌（如果剩余的牌数多于1张，则敌手可以掀开一张，这时挑战者并不会达到目标） 为了使敌手掀开最后一张牌，则只需保留一张牌，即保证挑战者掀开牌之后，剩余的牌数为4k+1即可，其中k为非负整数 在以上情况下，每一轮（指双方操作）后掀开四张卡牌即可保证挑战者一定获胜 看不懂？直接运行以下代码体验一下吧 直接使用devcpp运行以下代码即可，记得拓展名是cpp哦 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<iostream>using namespace...

之前一直听说零知识证明，但是一直没有学习过相关内容 今天在阅读陈教授的《Identity-based chameleon hashing and signatures without key exposure》一文中遇到了，故学习记录一下 知识证明和零知识证明知识证明是Proofs of Knowledge，零知识证明是Zero-Knowlegde Proof 二者之间有很多相似点，也有区别，具体如下 信息泄露的程度 知识证明中，通常证明着不会直接泄露密码，但是可能会提供一些有用的中间信息（例如密文的哈希值） 零知识证明中，验证者在验证的过程中，不能获得任何相关的信息，除了“证明者知道这个秘密” 应用场景 知识证明更侧重确认某人知道某个密码 零知识证明不仅确认某人知道某个密码，还确保验证过程中完全不会泄露任何相关信息 知识证明定义：证明者向验证者展示他们知道某个秘密值，但不一定完全隐藏这个秘密；关键在于，验证者能够确信证明者确实知道这个秘密值 离散对数知识证明Proof of Knowledge of a Discrete Logarithm 证明者拥有一个秘密值...

此博客为常驻，用于汇总笔者阅读《安全规约导论》一书的学习笔记 这本书里的好东西很多，价值很高，值得充分学习 持续更新中 安全规约前置知识 安全规约基础 荔枝成为BLS短签名糕守

密码学中数字签名方案的安全模型主要包括两种：存在性不可伪造（Existential Unforgeability against chosen-message attacks, EU-CMA）和强不可伪造（Strong Unforgeability against chosen-message attacks, SU-CMA）， 本文主要对比这两种安全模型。 两种安全模型都是通过敌手（Adversary）和挑战者（Challenger）之间的游戏（Game）来定义的。首先挑战者生成密钥对 $(pk,sk)$ 并发送 $pk$ 给敌手，自己保存 $sk$ 用来生成签名。敌手可以自适应地提交任意消息，挑战者根据敌手提交的消息生成对应的签名并返回给敌手。最后，敌手返回一个伪造的对未查询过的新消息的签名。 EU-CMA在数字签名里标准的安全模型 在该模型里，敌手可以非随机性地询问任意 message 的 signature 并对任意没有询问过消息的 message 进行 forgery...

阅读《Identity-Based Chameleon Hashing and Signatures Without Key Exposure》一文时，遇到了Decision Diffie-Hellman Problem (DDHP)这一概念，头一次遇到，便搜索了一下，打算学习学习；没想到捅了老挝——一个DH密钥交换算法能衍生出各式各样的东东 没办法了，学吧 由于种种原因（我比较懒），目前只学DDHP，其他的先挖个坑 DDHP论文里的描述 大致内容：在特定的群 $G_1$ 中，可以通过计算双线性映射的方式有效地判断一个四元组是否满足Diffie-Hellman条件 区别 DH DDHP 目的 用于密钥交换，建立安全通信 判断给定值是否符合Diffie-Hellman关系 功能 生成共享密钥 验证一个数值是否是由特定的私钥生成的 安全性基础 基于离散对数的困难性，安全性与密钥长度和生成元选择有关 直接依赖于离散对数问题的安全性，特别是在无法计算 $g^{ab}$...

数年之前就听闻莫反，FFT，NTT等数论变换的名称，但是一直未学习相关知识 最近学习后量子密码学，遇到了类似数论变换，辄学习一下 名词区分1、DFT(Discrete Fourier Transform)：离散傅立叶变换 $\rightarrow$ $O(n^2)$计算多项式乘法2、FFT(Fast Fourier Teansformation)：快速傅立叶变换 $\rightarrow$ $O(nlogn)$计算多项式乘法3、(F)NTT(Number Theoretic Transform)：（快速）数论变换 $\rightarrow$ 优化常数和误差，适用于整数域4、MTT(any Module NTT)：NTT的扩展 $\rightarrow$...

在 撬开后量子的大门 一文中，我们初步学习了后量子密码学，本篇博客，力求对后量子密码学进行进一步学习 量子计算我们通常说的量子计算就是通过量子逻辑门来操作处于叠加态的量子。比如Hadamard门，简称H门，他的一个主要功能就是通过计算基态产生等概率的叠加态。通过H门变换后的单量子叠加态为： $H(|Φ_1⟩)=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$ 两种基态的坍塌概率都为 $\frac{1}{\sqrt{2}}$，两个量子的H门得到的结果如下： $H(|Φ_2⟩)=\frac{1}{\sqrt{2^2}}(|00⟩+|01⟩+|10⟩+|11⟩)$ 每个态坍塌的概率 $\frac{1}{\sqrt{4}}$...

很早之前就听说ElGamal加密算法是一种公钥密码，但是具体实现和用途不甚了解，今天阅读了 A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS 一文，故去了解了一下。特开此文，记录一下 省流：ElGamal是DH密钥交换的抵抗中间人攻击版本 ElGamal加密算法是一个基于DH密钥交换的非对称算法，可以定义在任何循环群上，它的安全性取决于循环群上的离散对数难题 离散对数问题指的是： 已知 $a,b,n$ ，计算$ a^b\mod n$ 是简单的。 已知 $a,(a^b\mod n),n$ ，计算 $b$ 是困难的。 Diffie-Hellman 密钥交换过程： Alice 和 Bob选定一个素数 $p$ ，以及它的一个原根 $g$ Alice 选择一个密钥 $a$ ，计算 $A=g^a\mod p$ ，发给 Bob Bob 选择一个密钥 bb ，计算 $B=g^b\mod p$ ，发给 Alice Alice 计算 $s=B^a\mod p$ ，Bob 计算...

本文是 荔枝橙味拱腰觅马糕守 一文的后继，主要内容是对于 方案构造学习 一章中的 尝试发现方案构造错误 一节下的 30个经典方案的学习笔记 经过初次阅读尝试，发现笔者英文阅读能力较低，不足以在短暂时间内完成大量论文的阅读；故选择了在翻译器和人工智能的帮助下来进行阅读，以提升效率，并为第二次阅读打好基础 1984, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. [34]引言1976年，Diffie和Hellman首次提出了公钥密码的概念，并依赖离散对数问题和素数域上的计算复杂性来构造其密钥交换协议。ElGamal的工作正是基于这种思想，进一步提出了一个可以实现消息加密和解密的公钥加密系统，以及一个数字签名方案。 公钥密码系统公钥密码体制的基本思想是使用 Diffie-Hellman 密钥交换的基础 首先，通信双方选择一个大质数 $p$ 和生成元 $g$ ，这些参数都是公开的 然后双方分别选取自己的私钥（分别是 $x_A$ 和...