科学网 › 标签 › Adleman

标签: Adleman

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

沧海横流，谁开辟了DNA计算？: 热度 3 tangchangjie 2010-12-10 11:00; 沧海横流，谁开辟了DNA计算？----我所认识的L. Adleman(6) （唐常杰）　　是谁带来DNA分子的千军万马，是谁打开了生物计算机时代之门？　　其理念或前有渊源，但作出第一个能演示的DNA计算机原型的学者，是伦纳德·阿德曼（Leonard Adleman）。　　还是先讲故事，后作科普，把DNA计算科普放到本系列最后，是因它有点神秘，又有点长，要写得容易懂，还真费思量。博学深思出灵感下列取自对伦纳德·阿德曼的一次科学访谈录（意译）：　　“我是个一生都异想天开的人。　　“我躺在床上读Watson的基因分子生物学，DNA像一个四色项链， DNA双螺旋中两支上，碱基互补、聚合酶工作时，像图灵机的读写头游走于存储带 … 　　Wow! 它像计算机,它可以计算，我立刻起身下床，开始了思考…… 　　　　该出手时就出手敢想敢干、连远缘领域的艾滋病免疫都敢去客串一把的L.Adleman说干就干，于是就有了DNA计算实验室，于是就有了那张著名的狂热科学家的工作照：The mad scientist at work（参见系列博文之一）。天道酬勤，1994年，Leonard Adleman在论文中公布了它设计的第一个DNA计算机原型，成功解决了7城市8线路的旅行商问题。虽其速度不敢恭维，但它的生物属性令人眼睛一亮，DNA也可玩计算！展示了生物计算机的潜力，开辟了一个崭新的领域。　　　　 L.Adleman最初想象的工作场景：　 (a)一米见方的DNA计算机，成束的试管装着DNA汤，一个传统的硅片电脑控制着几十个机械手，不断地移动和和倾倒试管（最初实验中，阿德曼自己临时顶替了设想的机械手）；　 (b) 一系列生化过程（聚合链反应PCR等，详见科普部分）施加到这一锅DNA汤中N亿个DNA上，　 (c)用生命的力量计算。N亿个巧妙编码的DNA“麦片”在生化酶作用下，并行地、采用“人”海战术、用生命的力量，去碰撞、粘连，实现基因组合；几秒钟内，代表结果的DNA “麻花”（双螺旋）出现在这一锅DNA汤中。 (d)去粗存精，去伪存真，从DNA汤中的N亿个对象中，用一系列生化技术（包括超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等），取出那个代表结果的DNA，解释并输出结果，（详见后面科普部分）。　　 DNA计算的魅力。1立方米的DNA溶液可存1万亿亿比特数据；1立方厘米DNA溶液将超过1万亿片CD光盘的存储容量。速度可达到每秒10 20 次,耗能甚微。据称，以色列学者2001年研制出首台可编程DNA“微微”电脑，体积只一滴水的一万亿分之一，为进入人体奠定了基础。　　坚冰已经打破，航线已经开通。目前的DNA计算离实用尚远，还有太多的路要走，Leonard Adleman的工作展示了生物计算的可能性。DNA计算已成为全世界计算机科学家关注的新方向，有数百个团队在这里攻关竞争。　　当记者问Leonard Adleman，你是否意识到你已经开辟新的科学领域，他谦虚地说，这是两个学科，即计算机科学与分子生物学，自然结合的产物。　　他和分子生物学家Myron Goodman合作，建立了一个DNA计算和分子生物学的实验室。2001年获得发明专利。　　　　以子之矛攻子之盾 L. Adleman参与发明了RSA公钥技术（盾），又发明了DNA计算（矛）；以子之矛，攻子之盾，结果会如何？　　RSA公司 1978年悬赏100万美元征解,公开了公钥 (n, e )， 1995年4月26日，路透社报道， 600位专家，用1600台机器，用 8个月时间，把公布的129位整数 n分解为 p*q，求得d，构造出私钥。这说明129位不够长，不够安全。　　如果沿用上述的平台来破解256位的RSA，其计算量要大10 128 倍，如果没有方法上的革命，等它等到“天亦老”了。现在已有研究者提出用DNA 计算破译加密标准DES的方案，也有人雄心勃勃想用DNA计算的“人海战术”破解较小规模的RSA；在技术日新月异的今天，科学预言家一般不轻言某项基础研究“不实用”、某项技术“不可能”，但可说，近两年不太容易。　　用一锅DNA汤”来计算旅行商问题（以下为科普内容）　　拟用一个5城8线的旅行商问题来说明DNA计算的轮廓，此文利用了一些笔者过去的PPT页面，虽读过一点DNA计算文章，但未做过这方面的项目，理解自然就不深刻；初稿写好后，请了一位非计算机专业、亦非生物专业，但知识面较宽的大三学生来试读，他觉得难懂的地方或者删去，或者改写成了非标准的比喻（如DNA麦片，DNA麻花），失误之处，请专家指正。　　　　虚拟的“22世纪梦之旅”公司 . 此公司开辟了北京、天津、太原、郑州、济南五城的飞艇娱乐旅游，开张伊始，仅图1中箭头所示的8条航线。　　拟解决的问题：某人想从北京出发，游遍五个城市，到郑州结束，每城都要到且仅到一次，不考虑返程（例如，返程可在郑州坐火车）；请用DNA计算机找出一条合乎要求的旅游路线。　　　　　　　　　图1 DNA双螺旋碱基配对和 5城8线旅行问题　　问题中仅5城8线，不用计算机也可看出“北京-- 天津-- 太原-- 济南-- 郑州” 是一个正确答案。　　难度随城市数k呈指数增长，当城市数k很大时（例如10 4 数量级）,目前的高级硅片计算机+巧算法也会 “芯有余而速不足”。这是图论中的旅行商问题，是典型的NP完全问题。时下已有人宣称证明了“P不等于NP”，可能其证明或有瑕疵，但人们都倾向于相信这一结论，所以，NP问题是难计算的。　　而Leonard Adleman竟异想天开，要用“一锅DNA汤”来计算它。　　　　 (1) 准备工作，符号和编码长度　　DNA中有4种个碱基，其名称首字母是A、C、G、T；推荐一种助记法：gCat，Cat是猫，“g-猫”既时髦又响亮，词内的字母顺序能帮助记忆下列规则：构成DNA双螺旋时，G、C配对（或互补）， A、T配对（或互补）。　　DNA双螺旋的两个分支，就像阴模和阳模；DNA分裂--复制时，阴阳并行，像太极理论一样，1--2--4-- …--2^n,成指数的增长。　　如果一个汉字用三个字母表示，四个字母表达4^3=64个汉字，对我们这个小问题够用了。（大问题时，把编码加长）。本问题中，城市名含两汉字，用6个碱基表示。长度为6的编码可以区分 4^6=2^12=4096个对象，够用了。 (2) DNA麦片用DNA的4个碱基G、C、A、T给城市及已通航线编码。图2中，城市序列中的带框文字是5城市的编码，长度5X6=30;航线序列是已通航线中的4条，（其余4条航线未画出），其中头控和尾控是为了保证从北京开始，到郑州结束, 长度3+4X6+3=30。　　　　　　　　　　　　　　　　图2 5城4线的编码　　　　易见，按G与C互补、A与T互补的规则，航线编码串刚好是城市编码串的补码，两序列可绞成长为30的双螺旋结构（参见图1左边的双螺旋）。　　　　带框的字符串只含3个或6个碱基，较短小，好像是麦片（而不是长面条）；此问题5城8线，共需 5+8+2=15种DNA麦片，表达了5城8线和头尾控制，这些麦片可用专用设备制备，也可到专门的生化公司或研究机构订货，几毫升就有若干亿个。　（3）生命的力量使得DNA麦片汤变成麻花汤　　是金子就要放光芒，是生命，就要生长。　　把15种DNA麦片及其它必要的材料放在试管中，在正确的时间加入正确的酶（如限制内切酶、结合酶、转移酶、外切核酸酶、修饰酶），给以合适的温度压力，生命的奇迹发生了，亿万个麦片在DNA汤中翻滚、碰撞、粘连，最后变成一锅麻花汤。　　例如，代表北京和天津两个城市的麦片，通过互补的京天线，可连接成图3中的麻花中的一小段：　　　　　　　　　　　　　　　　图3 　　想象一下，图2的城市序列和航线序列分写两纸条，然后对准互补的碱基，搓绳一样绞起来。得到了什么？DNA双螺旋结构！参见图1左边的双螺旋。由于我们有控制头尾的麦片，CGA使头为北京； GGC 使得尾为济南；所以，这一锅DNA麻花表达了各种各样路径，且以北京开头，济南结尾。（这里简化了复杂的生化过程）。这是生命的礼赞，这是信息的演绎，这是DNA在计算！一条好消息：这一锅麻花汤中，肯定已了有若干这样的DNA双螺旋：代表了从北京到济南的、不重复城市的、且游遍了5城市、的正确的航线；当然，并不唯一。一条坏消息： DNA汤中也夹杂了其他不合格的线路，有的有重复城市，有的长度不合格，鱼龙混杂。 1994年，Adleman煮了一锅7城8线的DNA麦片汤，只用了几秒钟，就成了DNA麻花汤；但接下来，取其精华，去其糟粕的过程用了一个星期！用电泳技术，筛出长度合格的线路　　注意，DNA常带负电，用gel电泳技术，在上正下负的电场之下，不同长度的DNA受到不同的力，使得他们（在受力图上）像鸡尾酒一样分层，短的靠近上层，长的靠近下层，同长的在一层。　　有差别就有办法，通过适当的生物化学参数或技术，可取出长度为30（碱基数）的DNA，其双螺旋结构中，一支包含五个城市，另一只包含了4个航班。（可再参见图2）。　　筛选尚未成功，因长度为30（碱基数）的DNA中，五城可能有重复，（同时也就有遗漏），所以，L Adleman同志仍需努力。　　磁铁钓硬币的启示。有某农家乐，招揽游客向池中假山上“福”字投币祈福。每天傍晚，老板娘用钓鱼竿悬挂磁铁，把一元硬币钓出来，（因为一元硬币与磁铁有亲和力），而一分五分的铝币，则暂留水中招揽游客。映射到这里，老板娘不自觉地用了一种称为 “亲和力萃取”的高技术。　　　　 DNA麻花汤之钓鱼术用亲和力萃取技术（affinity purify），模仿上述老板娘，但把磁铁换为能吸引北京DNA 的材料，利用亲和力，可把包含北京碱基的、长度为30的DNA钓出来，放到缓冲池1中，再从缓冲池1中，把含天津碱基的DNA钓出来，…….,如此,流水线方式（串联地）地钓5次，则得到了含5个城市的DNA，都以北京开始，济南结束，且不重复不遗漏。五次钓鱼可比喻为过五关，过完五关，同时也“斩了四将” 得到四条航线。 Adleman做完去粗存精、去伪存真的过程用了一周。对大规模题目，可以用渐进 PCR方法，改进效率，（类似动态规划，保存并引用中间结果），减少时间代价。　　观察上述流程：DNA麦片--DNA麻花汤--电泳筛选-- DNA麻花汤中钓鱼，这就是DNA计算机解决5城市8线小规模旅行商问题的大致思路。　　一时间，学术界一片匪夷所思的感叹，一阵跟风追浪的潮流。　　什么是创新，这样的“无中生有”，就是创新；什么是掀起潮流？这样的“兴风作浪”就是掀起潮流！　关于L. Adleman的六篇系列博文到此结束，如果读者意犹未尽，请复习博文之二，　图灵奖得主是怎样炼成的--侧应钱学森之问，那里还留下了若干思考。该文最初被策划为系列之六，为了内容的由浅入深，才改为之二，请读者发表评论或博文来探讨和抒怀。科普文章中通俗和严谨不容易平衡，通常是宁可漏写，不可错写；失误之处，请专家指正。关于 Leonard . Adleman的系列博文　　 1 一位狂热科学家的工作照 2 图灵奖得主是怎样炼成的-----侧应钱学森之问 3 他凭什么得到图灵奖？（在RSA中的贡献，+RSA科普） 4 一不小心，成了计算机病毒的教父 (科普） 5 奇思妙想，客串艾滋病免疫研究 (科普） 6 沧海横流，谁开辟了DNA计算? （DNA计算简介，科普）其它系列博文的入口唐常杰博客主页科学博客主页参考文献 Adleman, L.M., Molecular computation of solutions to combinatorial problems, Science, 226, 1021-1024，(Nov. 11) 1994; 个人分类: 科普札记|17348 次阅读|14 个评论

奇思妙想，客串艾滋病免疫研究: 热度 1 tangchangjie 2010-12-9 09:53; 奇思妙想，客串艾滋病免疫研究--我所认识的 Leonard Adleman(5) （唐常杰）　　1991年，45岁的 L.Adleman客串艾滋病免疫领域，在关于艾滋病的的国际会议和学术期刊上发表了令人匪夷所思的奇思妙想。　　花开两朵，话分两头，先讲一个可诠释L Adleman关于艾滋病免疫之奇思妙想的园丁艺术。　　　　　　 1 农家乐中一棵桑。这可是亲眼所见，郊区一农家乐中有一桑树。两大枝，枝繁叶茂，俨然一个Y型的大伞。一日，风雨大作，桑树左枝上半，被折得骨断皮连，在风雨中颤抖。农家乐主人锯掉骨断皮连的左残支，同时把右边并未伤残的一支也锯得左边一样长，变成了对称的、但光秃秃Y字型。　　询问主人，桑也有生命。好比如人之左手断了，何以狠心把右手也砍断？主人说，桑有残肢，再生极快，（可能有某种反馈信号）；但它不能区分好枝与断枝，不会只长断枝而停长好枝，如不把两支锯得一样长，右支长得比左支还要快，很快使桑树不平衡，可能在下一次风雨中倾覆。(果然，半年后枝繁叶茂，体态端庄的桑树印证了主人理论的成功)。　　下面要说的Adleman关于艾滋病的免疫模型与此例挺相似。只是不知当年L. Adleman 在提出艾滋病免疫的妙想时候，是否也有这样的巧遇和巧喻。　　　　 2 人类免疫系统的狙击小组。　　在人的血液中有两类免疫细胞，带CD4的T-4，和带CD8的T-8。为了通俗，这里斗胆作个（也许是不太恰当的）比喻，二者联合组成消灭入侵者的狙击小组，T-4是只拿望远镜的观察手（负责记忆和识别）， T-8是拿枪的狙击手。　　狡猾的恐怖分子不和拿枪的狙击手对抗，而选择打掉拿望远镜的观察手，没有观察手的狙击小组就是半残废。　　在自然选择的压力下，突出重围的艾滋病病毒（HIV，Human Immuno-deficiency Virus），就像狡猾的恐怖分子，专门破坏T-4，从而破坏人的免疫力。　　　　 3 人类进化中过程的一个虚步病毒的狡猾是外因，人类得艾滋病，还有内因。不知是上帝的疏忽，还是过去几百万年的进化中过程中没有经历过艾滋病毒的洗礼，人的血液再生机制不能精细地对T-4（观察手）和 T-8（狙击手）区别和分别计数，如果艾滋病毒杀死100个T-4（观察手），再生机制将补充100个T细胞，新补充的细胞中，T-4和 T-8可能大致平衡，例如T-4， T-8各增50个。正常情况下，T细胞的总数是恒定的，按照L.Adelman的理论，没有损失的T-8（狙击手）也同等补充，就占用了T-4（观察手）的应有的补充份额，最后，使得T-8比正常多，而T-4（观察手）就比正常少；就会有若干狙击小组成半残废。长此以往，免疫力下降。下降到一定阈值，就是艾滋病；这就像那棵残废的桑树，右支比左比长，也好像一个军队残废的弱国，被各列强入侵欺凌；可能一场感冒，中招者就要驾鹤西去。　　　 4 客串艾滋免疫舞台 L. Adleman涉猎极广，一次他读了关于艾滋病病毒的论文，研究了在T-细胞上的作用机理，提供了一个免疫功能重建思路：当T-4减少时，人为地、在安全范围内，减少一些T-8，使得T-4细胞免疫重建过程中有足够的恢复空间，恢复到正常的平衡水平。　　真是反常规思维，真是匪夷所思！　　如果人的左手断了，把右手也砍掉，那是荒唐；但对T-4和T-8在免疫重建，却似乎可行。邻居的小孩观察昆虫的触须，说触须断了是可再生的，不需要截短另一支，可以单独再生复原。不知他观察是否正确。如果是，内在原因又是什么？请博友中这方面的专家解答。　　　　L.Adleman把这一奇思妙想写成了严肃的研究论文, 1991年发表了两篇关于艾滋病的国际会议和学术期刊上，笔者未查到被引用情况。1993和1996又发表了两篇这方面的论文，在google Scholar 上搜索，可查到其中一篇被引用75次，一篇被引用17次，给免疫功能恢复和重建提供了一个新的很活很野的思路。　　在这篇论文之后，有许多类似这一思路的工作，不知是否与L. Adleman客串的贡献有关，笔者是外行，不能擅议，需要请专家来评说。　无怪乎，当NetWorker记者（1996年8月）听了伦纳德·阿德曼的解释后，大呼 “Beautiful theory.” 的确是妙！感概：或许，L. Adleman在艾滋病免疫领域的贡献不足说道，但这说明了三点: ( a）敢想敢干敢客串。 L.Adleman那年45岁，在中国，是可以申请杰青和长江学者的年龄；他选择了开辟新路，探索多学科融合的路子，积累了生物、化学方面的基础，为后来在DNA计算方面的创新作好了准备。 (b) 学术环境宽松自由，如L. Adleman自己说的，“ 感谢这个的国度给我的科研自由, 允许我按照我认为的最好方式来工作 ” 。设若某管理机构以不容忍这样的跨学科客串，用类似SCI-EI的指标去限制他，可能就没有后来在DNA计算方面的创新了。 (c) 博友不妨取春晚心态。当客串演员站在这舞台”时，“掌声响起来, 要知道人家也是“经过多少失败，经过多少等待”，宽容地报以笑声，方显出你心更明白。这是L. Adleman从RSA的高峰，暂时低调迈出跨学科的步伐，再走向DNA计算高峰的真实历史，是在介绍DNA计算之前不能不写的环节。关于 Leonard . Adleman的系列博文　　 1 一位狂热科学家的工作照（ 2 图灵奖得主是怎样炼成的-----侧应钱学森之问） 3 他凭什么得到图灵奖？（在RSA中的贡献，+RSA科普） 4 一不小心，成了计算机病毒的教父 (科普） 5 奇思妙想，客串艾滋病免疫研究 (科普） 6 沧海横流，谁开辟了DNA计算? （DNA计算简介，科普）其它系列博文的入口唐常杰博客主页科学博客主页参考文献（感谢博友 eyuepeng 对参考文献的修订） Leonard Adleman, David Wofsy: Selective Depletion Of CD4+ T-Cells Elicits The Production Of CD8+ T-cells In Mice. Abstract. VII International Conference on AIDS. Flourence, Italy, (June) 1991. 　 Leonard Adleman, David Wofsy: T-cell Reconstitution Following Selective Depletion Of CD4+ T-cells. Abstract. Clinical Research, 39:2, 19. Leonard Adleman, David Wofsy: T-cell Homeostasis: Implications in HIV. JAIDS, 6(2):144-152. 1993. (被引用75次）. Leonard Adleman, David Wofsy: Blind T-cell homeostasis in CD4-deficient mice . J Acquir Immune Defic Syndr Hum Retrovirol 1996 Apr 1;11(4):334-40 (被引用17次）.; 个人分类: 人物故事|10278 次阅读|12 个评论

一不小心，成了计算机病毒的教父: tangchangjie 2010-12-8 09:26; 一不小心，成了计算机病毒的教父--- 我所认识的L. Adleman（4）(唐常杰）　　计算机病毒何许物也？　　在程序员眼中，计算机病毒是程序；对电脑用户，计算机病毒是祸害；当出现计算机故障时，计算机病毒是替罪羊；在某些不良分子手里，计算机病毒是摇钱树。　　还是先讲故事，谈计算机病毒与故事主人公的渊源，然后做科普。　　 Fred Cohen Leonard Adleman 　　为计算机病毒命名。 1983年，Leonard Adleman（阿德曼）的博士生，弗雷德·科恩（Fred Cohen）在他的指导下研究计算机网络安全相关的问题。这年11月3日科恩写出了可自我复制及感染能力的程序。兴奋地和阿德曼讨论。一周后，在11月10日的安全技术Seminar上，科恩展示了这个程序，此程序能在一个小时内传遍测试系统。　　给这一作品取个什么名称呢？Adleman涉猎甚广，有深厚的数学、化学和分子生物学基础，也是密码技术（特别是攻击技术）的编程高手兼科幻小说迷，联想到曾经在科幻小说上看到过“Computer Virus”，在那个讨论班上给这个程序命名为计算机病毒（Computer Virus），一不小心，就这样成了（现代）计算机病毒的教父。(问什么是教父？Google答：在婴儿或幼儿受洗礼时,赐以教名,并保证承担其宗教教育的人。)。　若干年后，Adleman还解释，Computer Virus这个term 不是他生造（Coined）的，是从科幻小说里面看来的。　　 “史前”计算机病毒 . 1971年, BBN的Bob Thomas 写过一个名叫Creeper的电报打字机控制程序（那时没命名为Computer Virus），受控制的电报打字机会发出信息: “我是Creeper,有本事来抓我(I'm creeper, catch me if you can!)”，由于其感染机理与现代计算机病毒有点差别，所以追认为”史前机器病毒”；博友 huangfuqiang 在第4条和第12条评论以及他推荐的文献中，补充了关于计算机病毒的比较完整的渊源。但正式给这类真实的程序命名为“Computer Virus ” 还是L. Adleman，所以，尚未听说过争夺教父这一名誉的官司。　　发表论文时的踌躇. 科学发现可以正面使用，也可被滥用。师徒俩反复讨论，怎样发表论文，发表多少，是否要把真正的代码公布，发表了是好还是坏，从技术讨论到了道德规范，…. 　　最后认为，把这一潜在的威胁告诉公众有好处，他俩分别于1987或1990发表了两篇著名的关于计算机病毒的论文。再后来，人们看到了下列事件： (a) 反病毒软件成为了一个产业，计算机病毒养活了这些产业；解决了一大批高技术人才的就业问题； ( b) ABC News,报道，在沙漠风暴中,美军施放计算机病毒，攻击伊拉克。 Adleman看到这两则消息后，回顾发表论文的功过是非，叹道：” Who knows(天晓得)！”。在那个给计算机病毒命名的Seminar进行时，笔者到南加大计算机系已10个月，年轻人们对这一发现的惊异、敬意、兴奋和热议都深深地印在脑中，播下了一颗七年后才萌发的种子。 1990年，计算机病毒在中国肆虐，我和我的同事们开发了一些反病毒软件，反病毒卡，写了一本专著《计算机反病毒技术》，有源程序、有理论分析、有数据库和知识库技术，由电子工业出版社出版。当然，现在回头去看这本10年前的书，肯定已年久失修，在当年可很火了一阵子，有一个月，此书被列在畅销书第二位，仅次于一本股票的书籍；还获得了1992年新闻出版署颁发的全国第六届优秀科技图书二等奖（那一年，有一个一等奖，得主是杨芙清院士；有两个二等奖）。想起来，真要感谢当年在南加大的机遇和早早埋下的种子。计算机病毒是怎样“活”起来，传染和破坏的？当《计算机反病毒技术》获新闻出版总署1992年全国优秀科技图书二等奖后，在领奖回程，第一次领略了首都出租车司机的健谈，师傅问，计算机怎么会怕病毒？会生霉吗？解释1 ：“计算机病毒是一种包含了复制自身指令的指令”，师傅摇摇头，太绕了，什么指令的指令….,惑而未解。解释2，一个发通知的例子，设出租车公司发了一个通知，“往下一车号传，今天下午两点钟开会”。注意，其中有三个要点： (a)“往下传”就是复制动作，只要执行这个指令，就会复制命令自身。 (b)“两点钟”是病毒的等待的时机； (c) 如果把行为“开会”换成“堵车”或其他不良动作，就成了消极代码或破坏性代码。师傅懂了，而且是从哲理的层次上理解的，可以认为是浅者见浅；专业人员立刻会联系到艰深的反病毒程序的汇编代码（遥想当年，工具不多，常用debug写），那是深者见深。如果深者和浅者都觉得自己理解了，这次科普就成功了。如今，计算机病毒和反病毒技术已今非昔比，在民用环境中，像瘟疫和防疫的对抗；在军事上，是信息导弹和信息反导弹的对抗。造病毒者挖空心思，反病毒者殚精竭虑；双方都从技术上升到了艺术阶段，其深入而精细代码已经不太容易作科普解释了。作为解释计算机病毒机理的实际例子，又要避免“教坏”，附录中，给出了在《计算机反病毒技术》中的一个古老的批处理病毒程序，它在DOS操作系统运行，可以把病毒从A;盘感染到到B:盘。此程序像已经灭活的疫苗，仅能演示思路，没实际害处了。关于 Leonard . Adleman的系列博文　　 1 一位狂热科学家的工作照 2 图灵奖得主是怎样炼成的-----侧应钱学森之问 3 他凭什么得到图灵奖？（在RSA中的贡献，+RSA科普） 4 一不小心，成了计算机病毒的教父 (科普） 5 奇思妙想，客串艾滋病免疫研究 (科普） 6 沧海横流，谁开辟了DNA计算? （DNA计算简介，科普）其它系列博文的入口唐常杰博客主页科学博客主页附录1在《计算机反病毒技术》中的自动执行程序 Autoexec.BAT，它在DOS操作系统运行，可以把病毒从A;盘感染到到B:盘。计算机病毒；（Autoexec.BAT ) //从A;盘复制到B:盘 Echo This is a Virus program IF exist b:\autoexec.bat goto Virus Goto No_Virus : Virus B: Rename autoexec.bat auto.bat //准备冒名顶替 Copy a:\autoexec.bat b: //自我复制部分 Echo I am Virus //诚实的自白 Del *.exe //实施破坏 : No_virus A: \Auto //调用原来 autoexec.bat，给出平安无事的假象参考文献 Fred Cohen ，Computer viruses : Theory and experiments ，puters Security Volume 6, Issue 1, February 1987, Pages 22-35 Leonard M. Adleman，An Abstract Theory of Computer Viruses ，Leonard M. Adleman，Lecture Notes in Computer Science, 1990, Volume 403/1990, Advances in Cryptology — CRYPTO’ 88 ，354-374, DOI: 10.1007/0-387-34799-2_28 唐常杰 ,胡军，计算机反病毒技术, 电子工业出版社,90年出版,93年修定版,.获92全国优秀科技图书二等奖. When did the term 'computer virus' arise? 来自科学美国网址，由博友 huangfuqiang 推荐。; 个人分类: 科普札记|14128 次阅读|15 个评论

他凭什么得了图灵奖？: 热度 3 tangchangjie 2010-12-7 10:07; 他凭什么得了图灵奖---我所认识的L . Adleman （3）（唐常杰） 1 幸运之星照耀有准备的头脑　　1976年，MIT的Rivest and Shamir 正在研究基于数论计算复杂性的新型密码技术；他们缺少扮演蓝军的研究者，Leonard .Adleman下列条件使得其他竞争者败下阵去： (a) UC Berkely的 EECS博士学位（文化底蕴与资质）； (b) 1975 -1976的三篇关于数论计算复杂性的论文（课题组急需的内功）； (c) 做过银行程序员，而且是编程高手（针对性极强的硬功）。　　　　黑白照片时代的RSA三剑客彩色照片时代的RSA三剑客　　　　　隐隐透出工作的疲惫笑意写在脸上，洋溢着丰收的喜悦　　Adleman本人在多年后（1996年8月）对NetWorker记者说，“我是在正确的地方，正确的时间，碰巧有正确知识的人”（ I was in the right place at the right time and, accidentally, had the right knowledge.）　　阳光好、土地肥、种子壮；基础、机遇、勤奋和经验，构成一个难能可贵的组合。　　舍他其谁也？　　他顺利地以讲师职称进入了Rivest and Shamir的密码技术研究团队,扮演蓝军，负责攻击。 2 RSA研究中的蓝军　　他们的攻防演习做了43 次，前42次蓝军胜，Adleman说，有些方案几分钟就破解了，有的用了几天。第43次，Rivest and Shamir，利用素数与整除性，构造了世界上第一个陷门单向函数，这个陷门之盾（详见本文科普部分），终于挡住了Adleman的才华之矛；用当时的计算机,要 long long time,成千上万年,才能破解。　　“红”方终于胜利了，这是红蓝双方的成功。　　他们先申请了专利，命名为 RSA公钥密码技术，在加州成立了RSA 数据安全公司，后来这个专利转到了MIT （猜测：因为这是职务发明，专利权归属学MIT学校）；1978年在顶级杂志CACM上发表了开创性的论文，于2002年三人共获图灵奖。　　 RSA最奇妙之点在于，互不相识的双方在不安全信道上，也能进行安全通信.其思想启发了今天的CA认证服务。因科普内容放在后面，这里暂用淘宝购物来比喻（实际上内涵不同），在淘宝上用支付宝购物，互不相识的买卖双方，通过第三方支付宝实现安全交易。　　说到这里，笔者想再次推荐在“ 基础、机遇、勤奋和成功 ”中中的哪个的积分公式，Leonard . Adleman正是这样一位基础好、路线对，勤奋而又有机遇的人，他成功了。 3 RSA公钥密码的用户感受先从用户感受来看这一发明的轮廓，把更深的原理放在附录2中，供有兴趣的朋友参考（其实，静下心来，用中学数学知识也能了解附录2的大概思想）。 ( a) 铸剑秘籍和鸳鸯剑传说中的铸剑师，得到了传说中的铸剑秘籍，制作了一对鸳鸯剑，形如y=f(x)和 x=g(y)；这两把剑刚好互为逆函数，即 x=g(f(x)), y=f(g(y))，真个是珠联璧合，天衣无缝；有下列特点： * 如果用y=f(x)加密，则可以用 x=g(y)解密，反之亦然； * 最终用户不必知道铸剑秘籍，就可使用鸳鸯剑； * 如只得到其中的一个，要想造出另外一个，知秘籍者易，不知秘籍者难，需要计算N万年。　　天下有这样的铸剑师，有这样的铸剑秘籍吗？　　有，而且办了公司，RSA公司就是这样的鸳鸯剑函数公司，批量生产（其生产流程参见附录2），对社会销售。一般人只能买鸳鸯剑函数，而买不到秘籍(正规名称：陷门、可理解为造钥匙的窍门，即一对秘密的大素数，参见附录2)。下面假定我们已经买回三对鸳鸯剑函数。 (b)公钥体制的大致思路。　　设x是明文，y是密文,有a,b,c三个户，他们从鸳鸯剑公司那里买回了自己的鸳鸯剑函数，鸳剑作公钥函数(让地球人都知道），鸯剑作私钥函数（妥善保管），用大写字母表示如下　　　　　公钥函数私钥函数　　　　　y=A(x), x=A -1 (y) 　　　　　y=B(x) , x=B -1 (y) , 　　　　　 y=C(x), x=C -1 (y) (c ) 用途1：举报罪犯。 a通过网络发信息x 给b，举报罪犯c；a当然不希望c知道，操作如下：　　a 把密文y=B(x)送给 B，　　b 收到密文y后，用x= B -1 (y)解密，即接受者用自己的私钥解密,得到明文x。　　即使c截获了y=B(x),也无法理解，因为要构造出函数B -1 ，相当于做因子分解，需要若干年。好像两位客家人用家乡话聊天，旁边的东北人即便听见了，也懂不起。 (d) 问题：举报后怎样领奖？如果是有奖举报，a凭什么领奖呢？ b说，的确收到了举报信息y=B(x)，凭什么说是a举报的呢？ (e) 增加发信者指纹，要点如下： * 为留下领奖凭据，a做了改进，把举报信息用改成 y=A -1 (B(x))，这好像在信封外再加一层信封; * b收到后，先用a的公钥y=A(x)函数脱去A -1 这层信封；注意，只有A自己才知道私钥函数A -1 (.. )，具有A -1 (…)这层信封的信息只能是A送来的，因此公钥密码体制还有防诬告，防抵赖的作用。 * b然后用自己的私钥B -1 解密。　以上就是公钥密码机制的思想，不需要微积分，需要若干数论中的关于整除性的定理；高三学生静下心来，也能理解思路框架，更多的技术细节的通俗解释在附录中，为通俗，有不到位的地方，请专家指正。 4《红灯记》要与时俱进传统的密码电报的密钥是密码本，需要单独的安全通道传送。截获与保卫密码本的斗争演绎出了许多可歌可泣的故事。现代京剧《红灯记》描写了抗日战争中，李玉和一家三代为保护密码本的故事，他们不怕牺牲、前赴后继，激励了几代人的革命激情。　　在公钥密码体制中，通信双方干脆公开自己的公钥，不怕敌人听到，而私钥静放囊中，不存在长途运送；所以，用人来传送密码本的故事，在未来战争中可能不会有了。　　爱国主义的主题是永存的，它将以新的形式存在和表达。在此意义上，《红灯记》也将与时俱进。　　附录1 天河一号超级计算机（10 15 次/秒）用穷举法分解200位大素数估计时间。通常的算法是 n=m (1/2) For (q=2；qn; q++)， If (q能整除m) { p=m/q; printf(“m分解为%d 和%d)\r\n”,p,q) } If (q==n) printf(“m本身是素数,不能分解\r\n”) 当m是一个200位的10进制整数时，for循环次数的数量级是10 100 ，用天河一号，每秒千万亿（10 15 ）次，还需要10 85 秒，假定一个聪明人找到一个好算法，把速度再提高十亿亿亿倍（10 25 ），还需要10 60 秒，一年不到10 9 秒，至少要10 51 年。（一年365x24x60x60=31536000秒 10 9 秒）附录2 陷门单向函数（鸳鸯剑函数）的制作下面的科普牺牲了严格性，希能使中学数学兴趣小组的朋友也看懂思路。 (a)双向函数 two-way function 　　三角函数y=Sin(x)的反函数是x=ArcSin(y)，对于基本三角函数，给定原来的函数f(x),不难找到反函数 f -1 （y）, 因为正反都容易，映射来去自由，所以称为双向函数。 (b) 单向函数 one-way function 　　单向函数y=f(x)有下列性质,如果给定x 1 ,求y 1 =f(x 1 )容易；反过来给定y 2 , 解方程y 2 =f(x) 求x 2 很难。（作为科普，就不费力地描述这个“很难”到底有多难）。乘法X与逆向运算因子分解InvX就是一对这样的冤家。给定两个100位的大素数p,q ，做乘法容易，对200位的合数做因子分解是一件难事（若干年）。附录1给了一个粗略的估计，如果用笨笨的穷举法，用高级计算机分解200位的大数，需要10 u 年，如果某聪明人吧方法加快了十亿亿亿（10 25 ）倍，只不过用v=u -25 取代了u，还要10 v 年。不解决根本问题。 ( c) 铸剑秘籍和鸳鸯剑传说中的铸剑师，得到了传说中的铸剑秘籍，制作了一对鸳鸯剑，形如y=f(x)和 x=g(y)；这两把剑刚好互为逆函数，即 x=g(f(x)), y=f(g(y))，真个是珠联璧合，天衣无缝；有下列特点： * 如果用y=f(x)加密，则可以用 x=g(y)解密； * 最终用户不必知道铸剑秘籍，就可使用鸳鸯剑； * 如只得到其中的一个，要想造出另外一个，知秘籍者易，不知秘籍者难，需要计算N年。 (d) 陷门单向函数 one-way function 　　RSA三剑客就是那个铸剑师；而那个秘籍，又称为陷门（或窍门），是一对大素数。为了做一对鸳鸯剑，需秘密地选一对数量级为10 100 的大素数p,q ，做乘法 n=pq；　　利用的整除性技术构造两个依赖于p和q的整数e 和 d ，(技术细节,参见 )， e 和 d 所藏身区间的大小的数量级是10 100 （穷举法搜索就死心了吧）。　　有了n,e, d,造出这一对互逆的鸳鸯剑（函数），一个做私钥，一个作公钥，如下： y = x e mod n , （做私钥） x = y d mod n （作公钥）　　教科书上，利用e,d的具体细节，可验证：x=（ x e mod n）d mod n= x ，即明文x 用鸳剑函数加密，而用鸯剑函数脱密，最后还原为明文，不失真。　　构造不是很复杂，计算起来也不慢；　　如只得到了鸳鸯剑之一，想造出另外一个，很难。因为关键是在数量级为10 100 的区间中找出 d或e, 但这需要把n分解为素数p,q, 如附录1的估计，这是难计算问题，现在的技术，要若干年。利用RSA原理，可开展鸳鸯函数租售业务，一般人只买鸳鸯函数，而不买秘籍(或陷门、即那一对素数)，这样，自己都不知道破解法，破解法被窃取的隐患就少一个。买回的鸳鸯剑，一个做私钥，自己保管好；一个作公钥，让地球人都知道。参考文献　 Leonard M. Adleman, Kenneth L. Manders: Computational Complexity of Decision Procedures for Polynomials (Extended Abstract) FOCS 1975: 169-177 　 Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Quadratic Polynomials STOC 1976: 23-29 　 Leonard M. Adleman, Kenneth L. Manders: Diophantine Complexity FOCS 1976: 81-88 　 . R. Rivest ， A. Shamir L.Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, 21(2):120-126,(February) 1978. 　博友 dailiangren （评论4）推荐的参考资料 ttp://zh.wikipedia.org/zh/RSA 加密演算法关于 Leonard . Adleman的系列博文　　 1 一位狂热科学家的工作照 2 图灵奖得主是怎样炼成的-----侧应钱学森之问 3 他凭什么得到图灵奖？（在RSA中的贡献，+RSA科普） 4 一不小心，成了计算机病毒的教父 (科普） 5 奇思妙想，客串艾滋病免疫研究 (科普） 6 沧海横流，谁开辟了DNA计算? （DNA计算简介，科普）其它系列博文的入口唐常杰博客主页科学博客主页; 个人分类: 科普札记|22046 次阅读|20 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: Adleman

相关帖子

相关日志

关闭安全验证