跳转至

others

  • 分类于 others
  • 需要 1 分钟阅读时间

解释 BB84 协议

背景

这周密码学课程，来自 BUPT 的高飞老师讲了一下 qkd 里的 BB84 协议，老师讲得很好，我也想记录一下这个协议的流程和方法。我不是这方面的专业人士，如果有什么问题请指出。

背景知识

QKD（Quantum Key Distribution）目的是让通信双方获得同一个密钥，它需要同时需要量子信道和经典信道。其中经典信道被认为是可信的，它可以被监听，但不能被中间人攻击。

在 BB84（Charles H. Bennett and Gilles Brassard (1984)）协议中，传输的是一个光子，它具有如下的特性：

可以用两个基去测量光子：➕️和✖️️，然后光子有四个偏振角度，分别是 ⬆️️ ⬇️️ ↘️️ ↗️️。定义一个二进制位和偏振角度的对应关系如下：

位 0 1 0 1
基 ➕️ ➕️ ✖️️ ✖️️
偏振角度 ⬆️️ ⬇️️ ↗️️ ↘️️

对于一个未知光子，可以用两种基进行测量，测量的结果：

偏振角度 ⬆️️ ⬇️️ ↗️️ ↘️️
用➕️测量 0 1 0/1 0/1
用✖️️测量 0/1 0/1 0 1

这里的 0/1 表示有 50% 概率测得 0，有 50% 概率测得 1。

协议流程

假如 Alice 要和 Bob 进行 BB84 协议。那么，Alice 首先随机生成一段二进制序列，并随机生成一个基的序列，以 Wikipedia 上的例子为例：

Alice's random bit 0 1 1 0 1 0 0 1
Alice's random sending basis ➕️ ➕️ ✖️️ ➕️ ✖️️ ✖️️ ✖️️ ➕️
Photon polarization Alice sends ⬆️️ ➡️️ ↘️️ ⬆️️ ↘️️ ↗️️ ↗️️ ➡️️
Bob 生成随机的基 ➕️ ✖️️ ✖️️ ✖️️ ➕️ ✖️️ ➕️ ➕️
Photon polarization Bob measures ⬆️️ ↗️️ ↘️️ ↗️️ ➡️️ ↗️️ ➡️️ ➡️️
Bob 认为的二进制信息 0 0 1 0 1 0 1 1
通过经典信道交换信息
Shared secret key 0 丢弃 1 丢弃 丢弃 0 丢弃 1

第一步，Alice 生成随机的二进制和随机的基，按照前面谈到过的对应关系，生成带有偏振角度的光子发给 Bob。

第二步，由于 Bob 只收到光子，不知道 Alice 选取的基底信息，而且只能用一个基测量一次，所以 Bob 随机从两种基选择一个来测量，得到了一串二进制。这些二进制里，如果 Alice 和 Bob 选取了同一个基，那么这一位的数据一定是对的；如果选取了不同的基，那么这一位有一半的可能是对的。总的来说，期望有四分之一的位是不正确的。

第三步，Alice 和 Bob 在 可信 的经典信道中把双方的基底进行对比，把基底相等的部分对应的二进制位提取出来，作为最终使用的密钥。

第四步，Alice 和 Bob 在最终使用的密钥中抽取若干位，然后对比，如果这些位都一致，则这个密码是有效的。如果错误率太高，那么很大概率是被攻击了。

安全性

协议的安全性，主要是靠量子的特性：未知量子态不可克隆、对未知量子态的测量可能会改变量子态。

假如在量子信道中间有一个 Eve 想要做坏事，它如果在中间观测了一下光子，它就会影响光子的量子态，导致 Bob 的密钥和 Alice 密钥会不一致，从而在协议的第四步被发现。并且，因为 Eve 并不知道 Alice 所使用的基底（假设 Eve 只能控制量子信道、不能控制经典信道），所以得到的二进制数据也有四分之一是不正确的。即使 Eve 尝试截获并且重发光子给 Bob，Bob 得到的密钥仍然有很高的错误率。通过这个错误率，就可以判断是否被攻击了。

另外，它的安全性还依赖以下几个方面：

  1. Eve 不能控制 Alice 和 Bob 的量子密码设备
  2. Alice 和 Bob 的随机数生成器需要足够安全
  3. 经典信道是可信的

引用

Quantum key distribution - Wikipedia

  • 分类于 others
  • 需要 1 分钟阅读时间

最近比较忙

最近一直没有更新我的 CS140e 系列文章，是因为最近一直忙于各种事情。等有空了再更新吧。

  • 分类于 others
  • 需要 1 分钟阅读时间

偶遇清华吴文虎教授

今天百团大战，正准备收摊的时候，天空工场那边来了一位长者，在和他们聊着什么。我很感兴趣，就上去听。老人大概已有八十高龄（后来查，是 1936 年生），但依然精神矍铄，首先和我们讲，作为工科的学生，一定在理解原理的基础上，多多去实践。他举了他自己的例子，他首先在电机系学习，后来，计算机系成立（当时还是自动控制系），他转到了计算机系，重新学起了计算机，说计算机编程学起来并没有什么难的。当年，苹果公司送过来了中国第一台 Apple-2，他们就把电脑拆了下来研究原理，又装上去继续工作。后来，他就在计算机系任教，教的正是《程序设计基础》这门课程。他十分重视实践，在第一年开课的时候就说，最关键的就是实践，安排了一些编程实验课，期中期末就是大作业。一开始有一些同学不重视实践，结果期末就挂科了。后来同学们就明白了实践的重要性，实践起来发现并没有那么难，最后就说，“吴老师，你说得对”。他又谈到了他的体育，他当年是北京长跑代表队的集训队选手，擅长一千五百米项目，他三千米只需要九分钟就能跑完。我们都感到自愧不如。我们说，现在的《程序设计基础》是徐明星老师在教，他说徐明星是他的博士生，邬晓钧也是他的博士生，他另外还有一个高徒我记不清楚了。他还是 IOI 中国队的前教练，听到我们有过一些 OI 基础，表示了赞许和鼓励。还有一些细节记不清楚了，记起来了再补充吧。

  • 分类于 others
  • 需要 2 分钟阅读时间

用 CPUID 获取评测机器的 CPU

受用 CPUID 检测各大 OJ 测评机所用的 CPU（以及日常黑 BZOJ）的启发，我决定去测试一下徐老师自己写的 OJ（名为 Tyche）所跑的机器是什么 CPU。于是我改造一下代码，用以下代码测评：

#include <stdint.h>
#include <iostream>
#include <time.h>
#include <cpuid.h>
#include <sys/time.h>
static void cpuid(uint32_t func, uint32_t sub, uint32_t data[4]) {
    __cpuid_count(func, sub, data[0], data[1], data[2], data[3]);
}
int main() {
    uint32_t data[4];
    char str[48];
    for(int i = 0; i < 3; ++i) {
        cpuid(0x80000002 + i, 0, data);
        for(int j = 0; j < 4; ++j)
            reinterpret_cast<uint32_t*>(str)[i * 4 + j] = data[j];
    }

    struct timeval stop, start;
    gettimeofday(&start, NULL);
    while(1) {
        gettimeofday(&stop, NULL);
        if(stop.tv_usec - start.tv_usec > (str[##EDITME##] - 32) * 10000)
            break;
    }
}

经过测试，usleep()和clock()都被封杀，但是gettimeofday()存活了下来。然后我就不断地C-a上面的###EDITME###，根据评测出来的时间推算出字符串，然后得到以下结果：

0 ~ 7 : PADDING
8 73 I
9 110 n
10 116 t
11 101 e
12 108 l
13 40 (
14 82 R
15 41 )
16 32 SPC
17 67 C
18 111 o
19 114 r
20 101 e
21 40 (
22 84 T
23 77 M
24 41 )
25 32 SPC
26 105 i
27 51 3
28 45 -
29 50 2
30 49 1
31 50 2
32 48 0
33 32 SPC
34 67 C
35 80 P
36 85 U
37 32 SPC
38 64 @
39 32 SPC
40 51 3
41 46 .
42 51 3
43 48 0
44 71 G
45 72 H
46 122 z

连起来就是这个 CPU：

Intel(R) Core(TM) i3-2120 CPU @ 3.30GHz

相比之下，还是比 BZOJ 好哈哈哈（又黑 BZOJ）。后来有大神在群里建议，可以用字符串比较的方式，对了就让题目 AC，不对就 WA。这个方法更加适合手里已经知道了一些常见 CPUID 的返回字符串，这里就是这样。

  • 分类于 others
  • 需要 1 分钟阅读时间

一个代替 Pulse Secure 客户端的工具

清华的校外 VPN 服务使用的是 Pulse Secure，所以在外网我们需要在客户端上安装 Pulse Secure 才能使用内网的 info 和网络学堂等网站。但是 Pulse Secure 一是非自由软件二界面难看，所以我找到了一个代替它的工具：OpenConnect.

安装后，输入以下命令：

sudo openconnect --user 你的学号 sslvpn.tsinghua.edu.cn --juniper --reconnect-timeout 60 --servercert sha256:398c6bccf414f7d71b6dc8d59b8e3b16f6d410f305aed7e30ce911c3a4064b31

然后输入你的 info 密码即可。

  • 分类于 others
  • 需要 1 分钟阅读时间

一个搞笑的伸展树的 Wiki

光哲同学在群里发了这个链接，特别搞笑，特此分享： 伸展树 - 百度百科

伸展树（Spaly Tree，事实上在国内 IO 界常常被称作 Tajarn 发明的 Spaly Tree，与此同理的还有 Terap），也叫分裂树，是一种二叉排序树，它能在 O(n log n) 内完成插入、查找和删除操作。它由 Daniel Sleator 和 Robert Tajarn 发现，后者对其进行了改造。它的优势可以不断伸展枝干（一个月 2~3 次），从而使树冠散开，提高光合作用效率。木材坚硬，是重要的经济类乔木。与其他植物不同的是，伸展树可以进行出芽生殖，繁殖速度极快。

  • 分类于 others
  • 需要 1 分钟阅读时间

回顾昨天的酒井知识竞赛

昨天晚上，我作为蒟蒻组的一员在三教 2102 参加了酒井知识竞赛，并因此鸽掉了 TUNA 和 Lab mU 的迎新会 hhh，不过运气好拿到了二等奖的好成绩，获得 Paperang 便携打印机一台。中间遇到了好一些网络方面的知识，这对于没有记忆 OSI 模型的我无疑有巨大的难度。下面是几道比较有印象的题目：

  1. 以下哪个不是编程语言？ A. J B. L C. R D. K 这题不难，R 肯定对，J 见过，K 略微有印象，选 B
  2. IPv6 链路层地址解析的协议是？ A. ARP B. Neighbour Solicitation C. Neighbour Advertisement D. Neighbour Discovery 对于一个没研究过 IPv6 的人来说这只好蒙了。。。ARP 是 IPv4 时代的，ND(Neighbour Discovery 则是 IPv6 时代的新产物，把 ARP 和 ICMP 等协议的功能都包含了进来，并且有新的功能。之前样题里还出现过问 IPv6 中去掉了 Unicast,Anycast,Multicast,Broadcast 中的哪种，答案是 Broadcast。
  3. 第一个把程序错误称做 bug 的是？ 选项太多忘了，答案是 Grace Hopper，因为当时一只飞蛾意外飞入了机器导致了故障，后来慢慢就流传下来了。
  4. 以下不是网络操作系统的是？ A. Windows NT B. OS/2 warp C. DOS D. Netware 当时我没见过 D，于是就选了。。。然后就挂了，Netware 是 Novell 开发的系统，OS/2 warp 当然是历史悠久的系统啦，而 DOS=Disk Operating System 所以没有“网络”二字。。。晕倒
  5. 以下是用作局域网的协议是？ A. TCP/IP B. IPX/SPX C. NetBEUI D. RS-232-C TCP/IP 当然不仅限于局域网，RS-232-C 是接口，当时蒙了 B 结果就对了，白白拿了 50 分哈哈哈。IPX/SPX 是 Novell 设计用在 Netware 系统上的局域网协议，NetBEUI 则是 NetBIOS 的一个历史遗留的一个“别称”。
  6. 姚期智的夫人给谁取了中文名？ 当然是 Donald Ervin Knuth 啦！高德纳万岁！
  • 分类于 others
  • 需要 1 分钟阅读时间

等时圆

最近学校老师讲了一下等时圆。先从这个题讲起：

在同一个地方向不同倾角光滑斜面用不同的初速度上滑，到达最高点所用时间相等，求最高点的轨迹是什么？

A. 直线 B. 椭圆 C. 抛物线 D. 圆

当时做这个题目的第一想法是把 x 和 y 座标表示出来：

\[ \frac{1}{2}gsin\theta{}t^2=l, y=lsin\theta, x=ycot\theta \]

然后就傻眼了，并得不到 x 与 y 的关系式。当然了可以求出几个点，强行带入二次曲线通式求解。不过想了想还是用解析几何的方法去做吧：

\[ \frac{1}{2}gsin\theta{}t^2=\sqrt{x^2+y^2}, sin\theta=\frac{y}{\sqrt{x^2+y^2}} \]

这么一代入，显然是圆。但既然这是物理题，可不可以用物理方法做呢？

可以，这就是等时圆。

啥叫等时圆？

等时圆就是，在一个光滑圆环上选择任意一点，让一个小球从这个点沿着光滑直杆到圆的最低点，无论这个点在哪里（最低点不算哈），时间都是一样的。怎么证明？

很简单：设小球与最低点连线与数值方向上夹角为\(\(\theta\)\)，那么

\[ s=2Rcos\theta, \frac{1}{2}gcos\theta{}t^2=s \]

你会发现 t 与\(\(\theta\)\)无关。证明完毕。

其实也可以倒过来：从圆的最高点往各个方向下滑，到达圆周时间相等。

好了，到此为止内容都没什么，但你会想问这和前面那道题目有什么关系呢？这怎么等时圆？重力往下诶。运动可是往右上方。

Here comes the black magic :)

我们考虑向下滑到最低点的那个等时圆，在这个圆周上滑倒最低点的时间都相等。好，我们把这个图沿着竖直方向旋转 180 度形成一个球，想想这个球上每一个点到最低点时间是不是也一样？那么考虑逆过程，让小球从斜面上滑下来，我对刚才的球体再竖着切一刀，得到的平面不就是题目中那个吗？得证。

当然了最好能有动画说明，限于本人时间问题暂时不提供 ^_^

  • 分类于 others
  • 需要 1 分钟阅读时间

The end of senior two

Finally the end of Senior 2 arrives. I'm on the way to Senior 3. The summer vacation is rather short which is really common in China. These days I have been diving into Emacs by subscribing both emacs and emacs-devel mailing list. It contributes to my English as well. I can learn a lot of new words and expression thanks to the nice and convenient feature of looking up a word in iOS.

  • 分类于 others
  • 需要 10 分钟阅读时间

Listen and write down subtitles of Cameron's speech

Here is the subtitle: 

We meet in a week that could change the United Kingdom for ever. Indeed, it could end the United Kingdom as we know it. On Thursday, Scotland votes, of the future of our country is at stake. On Friday, people could be living in a different country with a different place in the world and the different future ahead of it. This is the decision that could break up our family of nations and rips Scotland from rest of the United Kingdom. And we must be very clear, there is no going back from this. No re-run. This is a once and for all decision. If Scots vote 'yes', the U.K. will split and we will go on separate ways forever. When people vote on Thursday, they are not just voting for themselves, but for their children and grandchildren and the generations beyond. So I want to speak very directly to the people this country today about what is at stake. I believe I speak for millions of people across England, Wales, and North Ireland and many in Scotland too who would be utterly heart-broken by the break-up of the United Kingdom, utterly heart-broken to wake up on Friday morning, to the end of the country we love, to know that Scots will no longer join with the English, welsh-man, Irish, in the army, navy, and air force. [???] U.K. white celebrations and commemorations [???] U.K.'s fourteen teams in the Olympics to the British lines. The United Kingdom, would be no more, no U.K. pension, no U.K. passports, no U.K. pound. The greatest example of the [???] in the world have ever known of openness of people of different nationalities and face coming together as one, would be no more. It would be the end of the country that lodged the enlightenment(?) and abolished the slavery and drove the industrial revolution and defeated fascism. The end of a country that people around the world respect and admire. The end of a country that all of us call home. And you know what, we built this home together. It's only become Great Britain, because of the greatness of Scotland because of the thinkers the writers the artists the leaders the soldiers and inventors that make this country what it is. It's Alexander Fleming and David Hume J.K. Rowling Andy Murray and all the millions of people who play the part in this extraordinarily success story. The Scots who let the charge on pensions and the [???] and social justice we did all this together. For the people of Scotland to walk away now, we will be like painstakingly building a home and then [???] the door and throwing away the keys. So I would say that everyone voting on Thursday, please remember this is just [???] country. This is the United Kingdom. This is our country. And you know what makes it a truly great country, it is not a [???]. It is our values. British values. Fan of freedom, justice. The values that say wherever you are whoever you are, your life has dignity and worth. The values that say we don't work on by when the people are sick. We do not ask for your credit card in the hospital. We don't turn our backs when you get old and frail. We don't turn a blind eye or cold heart to people around the world from repair and cry and for help. This is what Britain means. This is what makes our country 'Yes the greatest on Earth'! And it is why millions of us could not bear to see that country ending for good for ever on Friday. Now i know that many people across Scotland were planning to vote yes. I understand why this might sound appealing. It is the promise of something different. I also know that the people who running the 'yes' campaign painting a picture of Scotland that is better than everywhere. And they can be good painting the picture. But when something looks too good to be true, that is usually because it is. And it's my duty to be clear about the lightly consequences of a 'yes' vote. Independence, would not be a trial separation but would be a painful divorce. As a Prime Minister, I have to tell you what that would mean. It would mean we no longer share the same currency. It would mean the arm forces we built up together over centuries being splitted up for ever. It would mean our pension funds being sliced up at some cost. It would mean the borders we have would become international and may no longer be so easily crossed. It would mean the automatic support that you currently get from British embassies when you are traveling around world the that would come to end. It would mean over half of Scottish [???] suddenly from one day to the next begin provided by banks in a foreign country. It would mean the interest rates in Scotland are no longer set by the bank with England's robust ability and security that promises. And it would mean for many banks that remain in Scotland, if they ever gotten to travel, it will be Scotish taxpayers and Scottish taxpayers and loan, that will bare the costs. It would mean that we no longer pull exhausted across the whole of out United Kingdom to pay for institutions [???] national health service or our welfare system. This is what guess work, there are no question marks, no maybe this, or maybe that. The nationalists want to break up U.K. funding on pensions, the U.K. funding on health care, the U.K. funding and comprehensive protection on national security. These are the facts. This is what would happen and end to the things that we should share together. And people in Scotland must know these facts before they make this once and for all decision. And one of the consequences is not to scare [???]. It is like warning a friend about the decision that they might take that will affect the rest of their lives and the lives of their children. I [???] this because I don't want the people of the Scotland to be sold a dream that disappears. Now I know that some people say we have heard about the risks and uncertainties, but we still want change. And look, the United Kingdom is not a perfect country. The country is, of course, constantly changing and improve people's lives. No one is content when there are still children living in poverty. No one is content when there are people struggling and the young people not reaching their full potential. And yes, of course, every political party is different, but all of us, all of us, conservatives, labor, [???], nationalists, we are all on a constant mission to change our country for the better. The question is, how to you get that change. And for me, it is simple. You don't get the change you want, by ripping your country apart. You don't get change by underlying your economy and damaging your businesses and diminishing your place in the world. But you can't get real concrete change on Thursday. If you vote 'no', businesses usual is not on the [???] paper. The status clown is gone. The campaign has swepted away. There is no going back to the way things were. A vote for 'no', means real change. If we [???] that change in practical terms, with a plan and a process. If we gotta know vote on Thursday that will trigger a major unpresidentive program of devolution with the [???] powers for the Scottish [???]. Major new powers will protest spending. Some welfare services will have agreed that time table for that stronger Scottish [???], a timetable for bringing that new powers that will go ahead in frozen [???]. White paper by November put into draft [???] by January, this is the timetable that is now agreed by all the main political parties in [???]. And I am prepared to work with all the main parties to deliver this during 2015. So a 'no' vote actually means faster, fairly, safer and better change. And this is vital point. Scotland is not a observer in this fairs of this country. Scotland is shaping and changing the United Kingdom for the better. Also did they [???] at any point in the last three hundred years. And Scotland will continue to help shape the constitution of our country. And Scottish people who enjoys the [???]  without losing the U.K. pension, the U.K. pound and the U.K. passport. Real change is Scotland's for the taking. The [???] and make [???] decisions but with this security and being in the United Kingdom and with idol risks of [???] alone. It is the both well or both worse. The Scotland's identity is your [???] strong Scottish culture, strong Scottish art, and strong [???] Scotland. And in the last fifteen years, you built a strong British [???]. Not all [???] institutions but a permanent one. So the vote on Thursday, it is not about whether Scotland is a nation. Scotland is a proud strong successful nation. The vote on Thursday is about two competing nations for Scotland's future. And that's the nationalist's vision. Narrowing down, going alone, breaking all ties with the United Kingdom. Or there is the patriotic vision, they strongs Scottish nation allied to the rest of the United Kingdom with its own strong Scottish Parliament. And it's hard. And with the benefit of working together in the U.K on [???] on pensions on health care funding, currency and interest rates. It is really the best of both wills. And it's the best way to get real change and secure a better future for your children and your grandchildren which all this vital debate is all about. [Clap Drink Water] And speaking of family, there is quite simply how I feel about all of this. We're a family. The United Kingdom is not one nation. We are four nations in a single country. That could be difficult but it is wonderful. Scotland, England, Welsh, North Ireland, different nations with individual identities competing with each other, even in time in raging each other. But It still mean so much stronger together. We're a family of nations. And why should the generations of that family be forced to choose whether to identiy only with their emperor or only with London. Why should they have to choose which embassy they want to go to when they are in trouble abroad. Or pack that passport when they go to see friends, loved ones and family. A family is not a compromise or second best. It is the magical identity that makes us more together than we can ever be apart. So please, do not break this family apart. In human relations, it is almost no good thing to turn away from each other to put up walls or score new lines on the map. Why should we take one Great Britain and turn it into separate smaller nations. What is that an answer to? How will that help ambitious young people who wanna make the mock on the world. Or [???] just want security. Or the family relying on jobs that will made in the U.K. Let no one fool you, that 'yes' is a positive vision. It is about dividing people. It is about closing doors. It is about making forigners our friends and family. That is not a optimistic vision. [Clap] The optimistic vision is about our family of nations staying together. Therefore, each other in the hard times, coming through the better times, we're just pulled through the great reception together. If we're not moving forward together, the road had been longer but it is finally lead upwards. And that's why I ask you to vote 'no' to walking away. Vote 'no' & you are voting for a bigger and broader and better future of Scotland. And you are investing in the future for your children and grandchildren. So this is our message to the people of Scotland: we want you to stay. Head hard and sow we want you to stay. Please don't mix up the temporary and permanent. Please don't think I am frustrated with politics right now and I just walk out of the door and never come back. If you don't like me, I won't be here for ever. If you don't like this government, it won't last for ever. But if you leave the United Kingdom, that will be for ever. Yes, the different parts of the U.K. do not always see eye to eye. Yes we need change, we'll deliver it. But to get that change together bright future would don't need to tear our country apart. [Yeah and Clap] In two days' time, this long campaign will be to an end. And you stand on the [???] of the billing board. I hope you ask yourself this: will my family and I truly be better off? By going alone? Will we really be more save and secure? Do I really want to turn my back on the rest of Britain? And why it is that so many people across the world asking why would Scotland want to do that? Why? And if you don't know the answers of these questions, then please vote 'no'. At the end of the day, all the eyes on this campaign can be rejuiced to a single fact. We are better together. As you reach your final decision, please, please, don't let anyone tell you you can't be a pride Scot and a pribe Brit. [Clap] Please, don't lose faith in what this country is and what we can be. Don't forget what a great United Kingdom you are a part of. Don't turn you back to what is the best family in the nations in the world. And the best hope for your family in this world. So please from all of us, vote to stick together, vote to stay, vote to save our United Kingdom. Thank you. [Clap and The End].

  • 分类于 others
  • 需要 1 分钟阅读时间

Start next term tomorrow

My term starts tomorrow. Sad. Homework haven't finished. I went to Guangzhou for GDKOI thie weekend, and i haven't known the result. It should be bad. I have no confidence at all. I may write less when this term starts. The second term of Senior 2 should a hard time for me. That's all. Sorry for the laziness.