Posted on | Post modified: | In

拉格朗日插值法

对某个多项式函数，已知有给定的k + 1个取值点：(x0,y0)...(xk,yk)
假设任意两个不同的xj都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：

l0 = (((x-x1)(x-x2)...(x-xk))/((x0-x1)(x0-x2)...(x0-xk)))*y0
    ...
lk = ...

f(x) = l0+l1...+lk即可求出多项式

example

已知3个点(4,10)(5,5.25)(6,1)

l0 = (((x-5)(x-6))/((4-5)(4-6))) * 10
l1 = (((x-4)(x-6))/((5-4)(5-6))) * 5.25
l2 = (((x-4)(x-5))/((6-4)(6-5))) * 1

f(x) = l0+l1+l2 = 1/4(x^2-28x+136)

Shamir 秘密共享

生成

Read more »

Posted on | Post modified: | In

前置知识 欧拉, 欧拉定理, 模反元素(模逆元) 可参见: RSA加密

阶

由欧拉定理可知，若n,a为正整数，且n,a互素（即gcd(a,n)=1），则 a^phi(n) = 1 (mod n)。
因此满足同余式 a^m = 1 (mod n)的最小正整数m存在，这个m称作a模n的阶，记作delta(n,a)。

原根

若n,a为正整数，且n,a互质，如果 gcd(a,n)=1 且 delta(n,a) = phi(n), 则称a为模n的原根.
简单来说，使该式成立的d可能有很多个值，又由欧拉定理可知delta(n,a) = phi(n)一定是满足的，如果此时所有delta(n,a)的可能取值中phi(n)是最小的，那么就称a为模n的原根。

eg:

a=3, n=7
可知 3,7互质, 所以phi(n) = 7 - 1 = 6
可得 3^6 = 1 (mod 7)

计算3^1, 3^2, 3^3, 3^4, 3^5 (mod 7) 都不等于1, 所以 6为满足 a^x = 1 (mod n)的最小正整数

delta(7,3) = 6 = phi(7), 可得 3为模7的原根

性质

Read more »

Posted on | Post modified: | In

流密码

密码学中，流密码（英語：Stream cipher），又譯為串流加密、資料流加密，是一种对称加密算法，加密和解密双方使用相同伪随机加密数据流（pseudo-random stream）作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流。实践中数据通常是一个位（bit）并用异或（xor）操作加密。

https://zh.wikipedia.org/wiki/流密码

  • chacha20/salsa20
  • rc4

块密码/分组密码

块密码只能对确定长度的数据块进行处理, 如aes每个块的大小必须为16, 如果不满16就需要进行padding

加密模式

ECB

最简单的加密模式即为电子密码本（Electronic codebook，ECB）模式。需要加密的消息按照块密码的块大小被分为数个块，并对每个块进行独立加密。

CBC

在CBC模式中，每个明文块先与前一个密文块进行异或后，再进行加密。在这种方法中，每个密文块都依赖于它前面的所有明文块。同时，为了保证每条消息的唯一性，在第一个块中需要使用初始化向量。

PCBC

填充密码块链接（PCBC，Propagating cipher-block chaining）或称为明文密码块链接（Plaintext cipher-block chaining），是一种可以使密文中的微小更改在解密时导致明文大部分错误的模式，并在加密的时候也具有同样的特性。

Read more »

Posted on | Post modified: | In

Golang Tun (gVisor)

import "gvisor.dev/gvisor/pkg/tcpip/stack" // gvisor

s := stack.New(stack.Options{
  NetworkProtocols:   []stack.NetworkProtocolFactory{ipv4.NewProtocol, ipv6.NewProtocol},
  TransportProtocols: []stack.TransportProtocolFactory{tcp.NewProtocol, udp.NewProtocol, icmp.NewProtocol4, icmp.NewProtocol6},
 })

ep := fdbased.New(&fdbased.Options{
   FDs:            []int{fd}, // fd: linux文件标识符, 如android中最后会获取到一个文件标识符
   MTU:            uint32(1500),
  })
 
 nicID := tcpip.NICID(s.UniqueID())
 if er := s.CreateNIC(nicID, ep); er != nil {
  ep.Attach(nil)
  return
 }

func isdns(opt *TunOpt, id stack.TransportEndpointID) bool {
 if id.LocalPort == 53 && (opt.DNSHijacking || id.LocalAddress.String() == opt.Gateway) {
  return true
 }
 return false
}

// TCP
 s.SetTransportProtocolHandler(tcp.ProtocolNumber, tcp.NewForwarder(s, defaultWndSize, maxConnAttempts,  func(r *tcp.ForwarderRequest) {
  wq := new(waiter.Queue)
  id := r.ID()

  ep, err := r.CreateEndpoint(wq)
  if err != nil {
   r.Complete(true)
   return
  }
  r.Complete(false)


  go func(local net.Conn, id stack.TransportEndpointID) {
   defer local.Close()

   if isdns(opt, id) { // 劫持一下dns
    /*
    * Handle DNS
    */
    return
   }

   target := net.JoinHostPort(id.LocalAddress.String(), id.LocalPort) // 远程目标地址
   nconn, er := net.Dial("tcp", target)
   if er != nil {
    return
   }
   defer conn.Close()
   utils.Relay(local, conn)
  }(gonet.NewTCPConn(wq, ep), id)
 }).HandlePacket)


// UDP
 s.SetTransportProtocolHandler(udp.ProtocolNumber, udp.NewForwarder(s, func(fr *udp.ForwarderRequest) {
    // handle udp, 和tcp差不多
 }).HandlePacket)

完整代码: tun

Android VPN Service

Android 的VPN Service只能处理Tun接口

class MyVpnService : VpnService() {
    override fun onStartCommand(intent: Intent?, flags: Int, startId: Int): Int {
        Builder().apply {
            setMtu(1500)
            setSession("my vpn")

            addAddress("172.19.0.1", 24).addRoute("172.19.0.2", 32)
            addAddress("fdfe:dcba:9876::1", 126)
                .addRoute("2000::", 3) // https://issuetracker.google.com/issues/149636790
                .addRoute("fdfe:dcba:9876::2", 128)

            addDnsServer("172.19.0.2") // 记得在Tun中劫持172.19.0.2:53处理所有的DNS请求

            addDisallowedApplication("com.example") // Disallowed和Allowed不能同时调用
            // addAllowedApplication("com.example")

            const fd = establish()
/*
    fd 为 linux文件标识符
    如果是通过tun2socks这种命令行工具处理
    需要使用Linux socket将fd发送给子进程
           
    如果是调用so动态库则不需要
    
    通过unix文件socket发送sd
      private fun sendFd(path: String) {
            LocalSocket().use { localSocket ->
                localSocket.connect(
                    LocalSocketAddress(
                        path,
                        LocalSocketAddress.Namespace.FILESYSTEM
                    )
                )
                localSocket.setFileDescriptorsForSend(arrayOf(fd)) // <------
                localSocket.outputStream.write(42)
            }
    }
*/
        }
        return START_STICKY   
    }


}

完整代码: VpnService

Posted on | Post modified: | In

质数

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。

来自 https://zh.wikipedia.org/wiki/质数

互质

互质是公约数只有1的两个整数，也可记gcd(a,b)=1, 叫做互质整数。

欧拉

在数论中，对正整数n，欧拉函数phi(n)是小于等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

来自 https://zh.wikipedia.org/wiki/欧拉函数

Read more »

Posted on | Post modified: | In

使用四年多的锤子手机越来越不堪重负，我决定换一款新的手机，在精心挑选后，选定了今年年初发布的一款Red MI手机，其极高的性价比打动了我。

使用

在收货当天就迫不及待下班回家开始把玩，有一个词可以形容我当时的体验：軽い。
换手机的契机也是如此，国产app越来越毒瘤，旧手机越来越卡，开启健康码和支付宝都要至少等待2秒。由于四年的落差，即使是一款性价比手机也让我觉得好流畅，还有120hz屏幕，令我爱不释手。

忍受

我知道MIUI是有广告的，但根据各种网上的说法，是有开关是可以关闭的。
所以我一入手就根据网上流传的各种方法将隐藏在系统不同角落的广告关闭了。
确实有效，APP和系统设置中的一些广告确实没有了，天真的我以为真的干掉了广告。
但是不定时广告推送，小米商城推送各种促销，系统自带浏览器也开始充当新闻客户端，各种推送傻逼新闻，而这一切的前提都是在我进入软件关闭各种推送的条件下，在了解后得知可以使用ADB冻结几个系统软件解决，我冻结了以下系统软件：

adb shell pm disable-user com.xiaomi.ab
adb shell pm disable-user com.miui.systemAdSolution
adb shell pm disable-user com.miui.analytics
adb shell pm disable-user com.sohu.inputmethod.sogou.xiaomi

确实有效，而且连某些app的开屏广告都没了。

愤怒

Read more »

Posted on | Post modified: | In

iptables chain

    +---------------------------------------------------------+
    |                   Network Card                          |
    +---------------------------------------------------------+
      |                                                    ^
      |                                                    |
      v                                                    |
 +----------+          is?      no    +-------+        +-----------+
 |prerouting| ----> localhost ------> |forward| ---->  |postrouting|
 +----------+          |              +-------+        +-----------+ 
                       | yes                                 ^
                       |                                     |
                       v                                     |
                    +---------+                        +-----------+
                    |  input  |                        |   output  |
                    +---------+                        +-----------+
                         |                                   ^
                         |                                   |
                         |                                   |
                         v                                   |
    +----------------------------------------------------------+
    |                        user                              |
    +----------------------------------------------------------+

out -> localhost: prerouting -> input
forward:          prerouting -> forward    -> postrouting
localhost -> out: output     -> postrouting

iptables table:

  • filter:
  • nat:
  • magle:
  • raw:
table <-> chain  
raw: PREROUTING, OUTPUT  
mangle: PREROUTING, INPUT, FORWARD, OUTPUT, POSTROUTING  
nat: PREROUTING, OUTPUT, POSTROUTING, INPUT  
filter: INPUT, FORWARD, OUTPUT

raw –> mangle –> nat –> filter  

chain <-> table
PREROUTING: raw, mangle, nat
INPUT: mangle, filter, nat
FORWARD: mangle, filter
OUTPUT: raw, mangle, nat, filter
POSTROUTING: mangle, nat

query

iptables -t <table> -nvL <chain>

iptables

Posted on | Post modified: | In

最近遇到了一件事, 让我又多熟悉了下HTTPS的相关内容, 先看看HTTPS的结构

通常的HTTP网络结构如下

+------+
| HTTP |
+------+
| TCP  |
+------+
|  IP  |
+------+
  ...

HTTP的的相关内容是通过TCP明文传输的, 如果有中间监听者, 可以直接看结相关内容.

HTTPS的结构

Read more »

Posted on | Post modified: | In

前言

最近一直在研究关于如何给一个fabric的组织更换一个新的证书, 包括所有加入的通道, 所有peer和orderer.
用了很多看似完美的方法却多次测试失败, 最后总算找到一种方法.

{
    "channel_group": {
        "groups": {
            "Application": {
                "groups": {
                    "Org1MSP": {
                        "groups": { }, 
                        "mod_policy": "Admins", 
                        "values": {
                            "MSP": {
                            }
                        }, 
                        "version": "0"
                    }, 
                    "Org2MSP": {
                        "groups": { }, 
                        "mod_policy": "Admins", 
                        "values": {
                            "MSP": {
                            }
                        }, 
                        "version": "0"
                    }
                }, 
                "version": "1"
            }, 
            "Orderer": {
                "groups": {
                    "OrdererOrg": {
                        "groups": { }, 
                        "values": {
                            "MSP": {
                            }
                        }, 
                        "version": "0"
                    }
                }, 
                "values": {
                    "ConsensusType": {
                        "mod_policy": "Admins", 
                        "value": {
                            "metadata": {
                                "consenters": [
                                    {
                                        "client_tls_cert": "==", 
                                        "host": "orderer.example.com", 
                                        "port": 7050, 
                                        "server_tls_cert": "=="
                                    }
                                ], 
                                "options": {
                                    "election_tick": 10, 
                                    "heartbeat_tick": 1, 
                                    "max_inflight_blocks": 5, 
                                    "snapshot_interval_size": 16777216, 
                                    "tick_interval": "500ms"
                                }
                            }, 
                            "state": "STATE_NORMAL", 
                            "type": "etcdraft"
                        }, 
                        "version": "0"
                    }
                }, 
                "version": "0"
            }
        }, 
        "sequence": "2"
    }
}

一个通道配置块类似上面这种,为了看的清楚有些内容我删了, 更换证书我们需要保证application及orderer的MSP是相同的, 否则更新配置块是不会成功的, 且我们得保证当前组织的raft节点的证书也要全部更换掉.

失败过程

Read more »