×

Loading...
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。

几个月前许诺要来详细的讲一下ECC加密过程,今天就开始来讲,ECC(椭圆曲线加密)比RSA复杂的多不过强度也高,而且最近比较忙,可能不会一直更新。

讲椭圆曲线加密,首先要从有限域(伽罗华域)开始说,所以先补充一些抽象代数的知识。

首先说一下有限域,有限域即存在一个有限数字n,=> 1+1+1+1+....+1 (n个)=0 在这个域上,其中1是identity elm.

讨论有限域我们只讨论乘法交换的有限域,即axb=bxa,所以因为其交换的特性,所以有限域必然是个Integral Domain.

则显然Integral Domain必然有性质 char(F)=m. (1+1+1....1=0, m个且m是最小个数)

现在我们来证明一个伽罗华域的一个重要特性,即GF(n) n必然是p^k形式,其中p是质数,而k是自然数。

要证明n是p^k形式,实际上必须先证明char(F)=m =p

如何证明呢?

当然是用反证法,假设有限域F的特征m不是一个质数,而是至少一个合数,则m=jk, 则显然,(j个)(1+1+...1)x(1+1+1.....+1)(k个)= (1+1+1+1+1.....+1) (m个)=0成立。

则显然 j或者k必然至少有一个是0,或者叫0 divisor. 则显然有限域是不可能存在非0的0 divisor的,所以矛盾。

所以m必然是一个质数p.

所以任何伽罗华域的特征只能是质数p.

则显然有限域的特征是p的情况下,有限域的集合数量只能是这个p^k的范畴。

证明完毕。

这个特性将在椭圆曲线做有限域同构映射时大量使用,记住结论即可。

Report

Replies, comments and Discussions:

  • 工作学习 / 学科技术 / 几个月前许诺要来详细的讲一下ECC加密过程,今天就开始来讲,ECC(椭圆曲线加密)比RSA复杂的多不过强度也高,而且最近比较忙,可能不会一直更新。 +3

    讲椭圆曲线加密,首先要从有限域(伽罗华域)开始说,所以先补充一些抽象代数的知识。

    首先说一下有限域,有限域即存在一个有限数字n,=> 1+1+1+1+....+1 (n个)=0 在这个域上,其中1是identity elm.

    讨论有限域我们只讨论乘法交换的有限域,即axb=bxa,所以因为其交换的特性,所以有限域必然是个Integral Domain.

    则显然Integral Domain必然有性质 char(F)=m. (1+1+1....1=0, m个且m是最小个数)

    现在我们来证明一个伽罗华域的一个重要特性,即GF(n) n必然是p^k形式,其中p是质数,而k是自然数。

    要证明n是p^k形式,实际上必须先证明char(F)=m =p

    如何证明呢?

    当然是用反证法,假设有限域F的特征m不是一个质数,而是至少一个合数,则m=jk, 则显然,(j个)(1+1+...1)x(1+1+1.....+1)(k个)= (1+1+1+1+1.....+1) (m个)=0成立。

    则显然 j或者k必然至少有一个是0,或者叫0 divisor. 则显然有限域是不可能存在非0的0 divisor的,所以矛盾。

    所以m必然是一个质数p.

    所以任何伽罗华域的特征只能是质数p.

    则显然有限域的特征是p的情况下,有限域的集合数量只能是这个p^k的范畴。

    证明完毕。

    这个特性将在椭圆曲线做有限域同构映射时大量使用,记住结论即可。

    • 老大,太小众了,给俺们这些小市民普及一下,学了这些能增加啥技能,将来能挣多少🤑,要不提不起兴趣。 +2
      • 我曾经在某个大厂因为这几个技能拿过$250usd/h的工作,其实工作中也没用到那么难的数学,但面试的人就招这类人,你说呢?嘿嘿嘿 +2
        • 膜拜一下,见到了比传说中的40万还牛的啦!俺也学习一下,给老板显摆显摆,看看工资能不能张个块儿八毛的。
          • 当年做的是algorithm architect的职位,一般只有这个职位需要面试这类问题。 +1
          • 如果会数据库优化的能拿更高,全世界懂这玩意的博士加起来也就两位数 +1
        • 面试的也希望碰到和他共同语言多的人
    • 补充一下为什么ECC加密开始代替RSA了。记不记得我前面一个贴子讲过RSA的安全是基于质因数分解这个NP问题的强度的。但2017年后随着2个新的快速数论筛法的出现,质因数分解的强度就大大降低了,所以目前都在往ECC靠了。 +1
      • 俺最近老是收到过GITHUB和BITBUCKET要求更改蜜月,是不是和这个有关呢?俺一直选择忽略,知道最后一刻。
        • 有可能,RSA理论上在快筛算法出现后,5年左右就要换密钥了,否则就不安全了。
    • 老大,你这个盖房龙潭吧,标题就改成: “学会这个,包你实现肉联40万的小目标!” +3
    • 前几年买了本抽像代数书看,当时就是为了想搞明白为什么五次方程没有根式解,不过只看了第一章就挌置了。
      • a^3+b^3=c^3此方程无整数解也叫费马大定理,这个定理的证明的关键就是东大本科生谷山峰提出的谷山峰猜想,就是模型式和复lattice上的椭圆曲线必然有一一对应。椭圆曲线这个非常偏门的数学分支因为一个猜想和现代计算机加密反而变成了热门的玩意。 +2
        眼睛打八折了。5此方程无解是伽罗华在群论上解决的。
        • 拓扑也有类似经历,当年拓扑刚开始时教授们说还看不到哪里能有用,没多少年集成电路兴起拓扑一下大热门 +1
      • 伽罗华就是琢磨这个问题,创建了群论。为“5次及以上的代数方程不可能有根式解”命题建立了严密的逻辑基础。
    • 老大,你给估一下,黎曼猜想能再人类上火星前给解决掉么?
      • 解决不了,数论的几个问题很可能在现有的一阶和二阶逻辑体系内是无解的,这是数学界普遍这么认为的。当然也可能有小概率会有非常非常偏门的解法,毕竟张益唐在孪生猜想做到了这点。但普遍认为数论问题没有研究意义就是因为没有解。 +1
        • 意思是说,我们的世界是不完备的?天啊!
          • 数学逻辑体系是有重大缺陷的,这个可能是个数学上的悲哀。造成大量的“事实”的东西,可能永远无法被证明,比如复杂度NP,P猜想,一大堆数论的猜想,只能用来用并且默认它是正确的,但想通过逻辑证明是不可能的。 +2
            • 说“悲哀”,说明人类看不到自己的渺小。人类信奉“眼见为实”,却没几个人知道自己对电磁波的感知波段宽度还不及有些飞鸟。太阳系在整个宇宙里只能是“微观世界”,在分析太阳系内行星运动时候,暗物质暗能量影响可以忽略不计
          • 没什么奇怪。”God never creates perfect world.”——伽利略从自制望远镜看到太阳居然有“黑点”时候说的。
    • 完全看不懂了,我连导数怎么求都忘了。厉害