[-]=======================================================================[-] Wizard Bible vol.53 (2011,10,12) [-]=======================================================================[-] x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ---- 第0章：目次 --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ○第1章: BSD環境におけるIPv6パケット送信手順 unya 著 ○第2章: 基礎暗号学講座・第25回 〜中国人剰余定理の応用〜 IPUSIRON 著 ○第3章: お知らせ ○第4章: 著者プロフィール x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第1章: BSD環境におけるIPv6パケット送信手順 --- 著者：unya x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに 　イーサネットで接続されたネットワークにおいて、ソケットAPIにたよらず完 全なIPv6パケットを構築して送信する方法について解説します。完全なIPv6パケ ットとは、IPv6拡張ヘッダーを含むパケットを指します。この方法により、API の制限を受けることなく、あらゆる形式のパケットを構築して送信することがで きるようになります。なお、今回はIPv6拡張ヘッダーについて触れず、パケット の送信のみに焦点をあてます。併せて、別途表記がないかぎり、すべてBSD系シ ステムを対象としています。GNU/Linuxなど非BSD系システムには当てはまらない 場合があります。 ■0x02.) 対象オペレーティングシステム 　下記のオペレーティングシステムを使用して、ヘッダーファイルの参照および サンプルコードのコンパイル・実行をおこないました。 ・Mac OS X 10.6.8(Snow Leopard) ・Mac OS X 10.7(Lion) ・FreeBSD 8.2 amd64 ・OpenBSD 4.9 amd64 ・NetBSD 5.1 amd64 ■0x03.) パケット送信におけるIPv6とIPv4のちがい ○3.1 socket(2)のプロトコル指定 　IPv4では、socket(2)の第3引数にIPPROTO_RAWを指定することでIPv4ヘッダを 含む完全なパケットを送信することができます。 ----- socket(PF_INET, SOCK_RAW, IPPROTO_RAW); ----- 　IPv6ではIPPROTO_RAWが特別な意味をもつことはありません。IPv6拡張ヘッダ ーを含む完全なパケットを送信するためには、リンクレイヤでパケットを送信す る必要があります。これを実現するためには、後述するBPFデバイスを使用しま す。socket(2)を使用して拡張ヘッダーを含むIPv6パケットを送信する場合は、 ソケットオプションを使用してパケットを構築する必要があります。しかし、こ の方法はAPIの制限を受けるため、カスタムパケットを送信する場合には適しま せん。 ○3.2 バイトオーダー 　IPv4では、IPヘッダーの各フィールドのバイトオーダーについて明文化されて いませんでした。そのため、オペレーティングシステムの仕様に合わせてバイト オーダーを考慮した設定をおこなう必要がありました。これに対して、IPv6では すべてネットワークバイトオーダーでIPv6ヘッダーの各フィールドを設定します。 ■0x04.) イーサネットヘッダー 　リンクレイヤは、OSI参照モデルのデータリンク層を指します。今回はイーサ ネットで接続されているネットワークを想定しているため、データリンク層でや り取りをおこなう際に参照されるイーサネットヘッダーの構造を知っている必要 があります。 ○4.1 イーサネットヘッダーの構造 　イーサネットヘッダーは、48ビットの送信先MACアドレス、48ビットの送信元M ACアドレスおよび16ビットのイーサネットタイプから構成されます。 ----- 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination MAC Address | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Source MAC Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----- Destination MAC Address 48ビットの送信先MACアドレスです。 Source MAC Address 48ビットの送信元MACアドレスです。 Type ペイロードのタイプを示します。IPv6であれば、ここは0x86ddになりま す。 この値はFreeBSDとMac OSではnet/ethernet.h、OpenBSDとNetBSDではne t/ethertypes.hで定義されています。 ----- #define ETHERTYPE_PUP 0x0200 /* PUP protocol */ #define ETHERTYPE_IP 0x0800 /* IP protocol */ #define ETHERTYPE_ARP 0x0806 /* Addr. resolution protocol */ #define ETHERTYPE_REVARP 0x8035 /* reverse Addr. resolution protocol */ #define ETHERTYPE_VLAN 0x8100 /* IEEE 802.1Q VLAN tagging */ #define ETHERTYPE_IPV6 0x86dd /* IPv6 */ #define ETHERTYPE_PAE 0x888e /* EAPOL PAE/802.1x */ #define ETHERTYPE_RSN_PREAUTH 0x88c7 /* 802.11i / RSN Pre-Authentication */ #define ETHERTYPE_LOOPBACK 0x9000 /* used to test interfaces */ ----- 　イーサネットヘッダーの構造体は、FreeBSDとMac OSではnet/ethernet.h、Ope nBSDではnetinet/if_ether.h、NetBSDではnet/if_ether.hで定義されています。 ----- /* * Structure of a 10Mb/s Ethernet header. */ struct ether_header { u_char ether_dhost[ETHER_ADDR_LEN]; u_char ether_shost[ETHER_ADDR_LEN]; u_short ether_type; }; ----- ■0x05.) IPv6ヘッダー ○5.1 IPv6ヘッダーの構造 ----- 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| Prio. | Flow Label | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload Length | Next Header | Hop Limit | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + Source Address + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + Destination Address + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----- Version IPv6のバージョンです。ここは6が入ります。 Priority 優先度。IPv4でいうところのTOSにあたります。 Flow Label フローラベル。パケットの識別用に用いられますが、今のところ明確な 規定はありません。 Payload Length IPv6ヘッダーに続くペイロードサイズです。拡張ヘッダーもペイロード サイズに含まれます。 IPv6ヘッダーのサイズは含まないので注意が必要です。 Next Header IPv6は数珠つなぎのようにしてヘッダーを拡張させることができます。 ここには、後続のヘッダー種別が入ります。 Hop Limit IPv4でいうところのTTLです。 Source Address 送信元IPアドレス。128ビットです。 Destination Address 送信先IPアドレス。128ビットです。 　IPv6ヘッダーにはチェックサムはなく、すべて上位レイヤーに任せます。 　IPv6ヘッダーはnetinet/ip6.hで定義されています。 ----- /* * Definition for internet protocol version 6. * RFC 2460 */ struct ip6_hdr { union { struct ip6_hdrctl { u_int32_t ip6_un1_flow; /* 20 bits of flow-ID */ u_int16_t ip6_un1_plen; /* payload length */ u_int8_t ip6_un1_nxt; /* next header */ u_int8_t ip6_un1_hlim; /* hop limit */ } ip6_un1; u_int8_t ip6_un2_vfc; /* 4 bits version, top 4 bits class */ } ip6_ctlun; struct in6_addr ip6_src; /* source address */ struct in6_addr ip6_dst; /* destination address */ } __attribute__((__packed__)); ----- ■0x06.) IPv6パケットの送信 ○6.1 リンクレベルでのパケット送信手順 　リンクレイヤでパケットを送信するためには、パケットを送信するためのBPF デバイスを開き、出力インタフェースと関連づける必要があります。その後、パ ケットの構築および送信処理をおこないます。 ○6.2 BPFデバイスを開く 　BPF(4)はリンクレベルでパケットの読み書きをおこなうためのデバイスです。 /dev/bpfNがそのデバイスで、Nの部分はBPFデバイスの番号となります（/dev/bp f0のように）。BPFデバイスはopen(2)で開きます。 ----- bpfd = open("/dev/bpf0", O_RDWR, 0); ----- 　送信元MACアドレスをスプーフする場合は、オペレーティングシステムによっ て送信元MACアドレスが上書きされないようにする必要があります。 ----- int spoof = 1; #if defined(BIOCGHDRCMPLT) && defined(BIOCSHDRCMPLT) if (ioctl(bpfd, BIOCSHDRCMPLT, &spoof) < 0) { fprintf(stderr, "ioctl(BIOCSHDRCMPLT)"); exit(1); } #endif ----- ○6.3 出力インタフェースとBPFデバイスを関連づける 　パケットを出力するインタフェースを決定し、BPFと関連づける必要がありま す。em0を出力インタフェースとするのであれば、以下のようなコードになりま す。 ----- struct ifreq ifr; bpfd = open("/dev/bpf0", O_RDWR, 0); memset(&ifr, 0, sizeof(ifr)); strlcpy(ifr.ifr_name, "em0", sizeof(ifr.ifr_name)); if (ioctl(bpfd, BIOCSETIF, &ifr) < 0) { perror("ioctl(BIOCSETIF)"); exit(1); } ----- ○6.4 パケット送信 　送信はwrite(2)を使用してBPFデバイスへ書き込みます。構築したパケットの バッファをoutpack、サイズをpacketsizeとすると以下のようなコードになりま す。 ----- write(bpfd, outpack, packetsize); ----- ■0x07.) サンプルコード 　以下、サンプルコードを掲載します。エラー処理は大幅に省略しています。 ----- /* * IPv6 UDPパケット送信サンプルコード * * 以下のOSにてコンパイル・動作を確認済み * Mac OS X 10.6.8 * Mac OS X 10.7 * FreeBSD 8.2 amd64 * OpenBSD 4.9 amd64 * NetBSD 5.1 amd64 * * root:~# ./a.out en0 1:2:3:4:5:6 6:5:4:3:2:1 2001:db8::1 2001:db8::2 * Sending 126 bytes ... 126 bytes sended. * * Using bpf device : /dev/bpf1 * Interface : en0 * Source ether : 1:2:3:4:5:6 * Destination ether: 6:5:4:3:2:1 * Source ip : 2001:db8::1 * Destination ip : 2001:db8::2 * Source port : 40000(0x9c40) * Destination port : 54321(0xd431) * * 0 1 2 3 * 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 * -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ * 06050403020101020304050686dd60000000004811fa20010db8000000000000 * 00000000000120010db80000000000000000000000029c40d431004800004141 * 4141414141414141414141414141414141414141414141414141414141414141 * 414141414141414141414141414141414141414141414141414141414141 * * root:~# */ #include #include #include #include #include #include #include #include #include #include #include #if defined (__OpenBSD__) # include # include #elif defined (__NetBSD__) # include # include #else # include #endif #include #include #include #include #include #include #include #include #include #define BPFMAX 255 #define DEFAULT_SPORT 40000 #define DEFAULT_DPORT 54321 #define PACKETSIZ 60000 static void hexdump(char *p, size_t len) { unsigned int i, s; int nshorts; nshorts = (unsigned int)len / sizeof(unsigned short); i = 0; printf("\n"); printf(" 0 1 2 3\n"); printf(" 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1\n"); printf("-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"); while (--nshorts >= 0) { if ((i++ % 16) == 0) printf("\n"); s = *p++; printf("%02x%02x", s & 0xff, *p++ & 0xff); } if (len & 1) { if ((i % 8) == 0) printf("\n"); printf(" %02x", *p); } printf("\n\n"); } static void usage(void) { fprintf(stderr, "Usage: ip6udp \n"); exit(1); } static size_t ip6udp_build(char *outpack, const char *p, size_t plen, struct sockaddr_in6 *src, struct sockaddr_in6 *dst, unsigned short sport, unsigned short dport) { struct ip6_hdr *ip6; struct udphdr *udp; size_t packetsiz, payloadsiz; payloadsiz = sizeof(struct udphdr) + plen; packetsiz = sizeof(struct ether_header) + sizeof(struct ip6_hdr) + payloadsiz; ip6 = (struct ip6_hdr *)(outpack + sizeof(struct ether_header)); ip6->ip6_vfc = IPV6_VERSION; ip6->ip6_plen = htons(payloadsiz); ip6->ip6_nxt = IPPROTO_UDP; ip6->ip6_hlim = 0xfa; ip6->ip6_src = src->sin6_addr; ip6->ip6_dst = dst->sin6_addr; udp = (struct udphdr *)(outpack + sizeof(struct ether_header) + sizeof(struct ip6_hdr)); udp->uh_sport = htons(sport); udp->uh_dport = htons(dport); udp->uh_ulen = htons(sizeof(struct udphdr) + plen); udp->uh_sum = 0; memcpy((char *)(udp + 1), p, plen); return packetsiz; } static void my_ether_aton(const char *p, unsigned char *buf) { struct ether_addr *eap; if ((eap = ether_aton(p)) == NULL) { fprintf(stderr, "%s: invalid ether address\n", p); exit(1); } memcpy(buf, eap, sizeof(struct ether_addr)); } static void ether_build(char *outpack, unsigned short ether_type, struct ether_header *e) { struct ether_header *ether; ether = (struct ether_header *)outpack; memcpy(ether->ether_dhost, e->ether_dhost, ETHER_ADDR_LEN); memcpy(ether->ether_shost, e->ether_shost, ETHER_ADDR_LEN); ether->ether_type = htons(ether_type); } int main(int argc, char *argv[]) { char outpack[PACKETSIZ], bpfname[sizeof("/dev/bpf####")]; char *udppayload; char *sourceif = 0, *sourceip = 0, *destip = 0; char *sourceeth = 0, *desteth = 0; struct ifreq ifr; int spoof = 1, i, snddev, error, r; unsigned long sport = DEFAULT_SPORT, dport = DEFAULT_DPORT; size_t plen = 64; /* udp payload data length */ size_t packetsiz; struct sockaddr_in6 src, dst; struct addrinfo *res, hints; struct ether_header eh; if (argc != 6) usage(); sourceif = argv[1]; sourceeth = argv[2]; desteth = argv[3]; sourceip = argv[4]; destip = argv[5]; my_ether_aton(sourceeth, eh.ether_shost); my_ether_aton(desteth, eh.ether_dhost); if ((udppayload = malloc(plen)) == NULL) { perror("malloc"); exit(1); } memset(udppayload, 'A', plen); /* 送信用デバイス設定 */ for (i = 0; i < BPFMAX; i++) { sprintf(bpfname, "/dev/bpf%d", i); if ((snddev = open(bpfname, O_RDWR, 0)) > 0) break; } if (snddev < 0) { perror("open(bpf)"); exit(1); } #if defined(BIOCGHDRCMPLT) && defined(BIOCSHDRCMPLT) if (ioctl(snddev, BIOCSHDRCMPLT, &spoof) < 0) { fprintf(stderr, "ioctl(BIOCSHDRCMPLT)"); exit(1); } #endif /* bpfと送信インタフェースを関連づける */ memset(&ifr, 0, sizeof(ifr)); strlcpy(ifr.ifr_name, sourceif, sizeof(ifr.ifr_name)); if (ioctl(snddev, BIOCSETIF, &ifr) < 0) { perror("ioctl(BIOCSETIF)"); exit(1); } /* 送信先アドレス */ memset(&hints, 0, sizeof(hints)); hints.ai_family = PF_INET6; hints.ai_socktype = SOCK_RAW; hints.ai_protocol = IPPROTO_UDP; hints.ai_flags = AI_CANONNAME; error = getaddrinfo(destip, NULL, &hints, &res); if (error) { fprintf(stderr, "ip6udp: %s: %s\n", destip, gai_strerror(error)); exit(1); } memcpy(&dst, res->ai_addr, res->ai_addrlen); freeaddrinfo(res); /* 送信元アドレス */ memset(&hints, 0, sizeof(hints)); hints.ai_family = PF_INET6; hints.ai_socktype = SOCK_RAW; hints.ai_protocol = IPPROTO_UDP; hints.ai_flags = AI_CANONNAME; error = getaddrinfo(sourceip, NULL, &hints, &res); if (error) { fprintf(stderr, "ip6udp: %s: %s\n", sourceip, gai_strerror(error)); exit(1); } memcpy(&src, res->ai_addr, res->ai_addrlen); freeaddrinfo(res); /* フレーム構築 */ memset(outpack, 0, sizeof(outpack)); ether_build(outpack, ETHERTYPE_IPV6, &eh); packetsiz = ip6udp_build(outpack, udppayload, plen, &src, &dst, sport, dport); /* IPv6パケット送信 */ fprintf(stderr, "Sending %lu bytes ... ", packetsiz); if ((r = write(snddev, outpack, packetsiz)) != packetsiz) { perror("write"); exit(1); } fprintf(stderr, "%d bytes sended.\n\n", r); fprintf(stderr, "Using bpf device : %s\n", bpfname); fprintf(stderr, "Interface : %s\n", sourceif); fprintf(stderr, "Source ether : %s\n", ether_ntoa((struct ether_addr *)eh.ether_shost)); fprintf(stderr, "Destination ether: %s\n", ether_ntoa((struct ether_addr *)eh.ether_dhost)); fprintf(stderr, "Source ip : %s\n", sourceip); fprintf(stderr, "Destination ip : %s\n", destip); fprintf(stderr, "Source port : %lu(0x%.4x)\n", sport, (int)sport); fprintf(stderr, "Destination port : %lu(0x%.4x)\n", dport, (int)dport); hexdump(outpack, packetsiz); return r; } ----- ■0x08.) 参考文献 [1] RFC 2460 - Internet Protocol, Version 6 (IPv6) Specification [2] RFC 3542 - Advanced Sockets Application Program Interface (API) for IPv6 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第2章: 基礎暗号学講座・第25回 〜中国人剰余定理の応用〜 --- 著者：IPUSIRON x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに 　連立合同方程式を解くためのアルゴリズムとして、中国人剰余定理が存在する ことをWB35で紹介した。しかし、このアルゴリズムについてまだ具体的に説明し ていなかったので、今回は中国人剰余定理の定義とそのアルゴリズム、そして応 用について紹介したい。 ■0x02.) 簡単な連立合同方程式を解く 　x≡a (mod 5)かつx≡b (mod 7)を満たすxを計算したいとする。即ち、5で割っ た余りがaで、7で割った余りがbとなるxを求めればよい。 　(5,7)=1より、∃p,q∈Z s.t. 5p+7q=1 　これを満たす(p,q)は(p,q)=(-4,3),(3,-2),…である。 　ここで、(p,q)=(-4,3)を代表して考える。 　このとき、 5(-4)+7(3)=1 -20+21=1 mp+nq=1　（ここでm=5,n=7,p=-4,q=3とおいた） x=21a-20b(=nqa+mpb)とおく（x=mpa+nqbではないことに注意）。 [1]x=21a-20b≡1・a+0・b (mod 5)≡a (mod 5) [2]x=21a-20b≡0・a+1・b (mod 7)≡b (mod 7) 　よって、このxは答えになっている。 ■0x03.) 中国人剰余定理 　上記では2つの1次合同方程式において法が具体的に指定されていた。実は、法 をm,nのように変数化しても、同様にして解xを求めることができる。 　まずは法がmnの解がただ1つだけ存在することを証明する。 [定理] (m,n)=1、m,n∈Nとする。 このとき、x≡a (mod m)かつx≡b (mod n)を満たす整数xはmnを法として、ただ1 つ存在する。 [証明の方針] 　いきなり証明をする前に、少しの一般性を下げた状態を眺めてみる。 　a,b,m,nの4つの変数（m,nは制限あり）があるので、ここでは自由度の高いa,b に具体的な値を入れておく。どうせ値を設定するなら、極端な設定にした方が問 題解決に繋がりやすい。例えば、a,bについて、0,1を設定してみる。 　ここで、a=1,b=0の場合を考える。 ・x≡1 mod m ・x≡0 mod n 即ち、 ・x=1+sm ・x=rn 　ここで、r,s∈Zとした。 　よって、1+sm=rnなので、-sm+rn=1が成り立つ。 　これはm,nに対して、拡張ユークリッド互除法を適用して得られる式と同じであ る。 　逆にいうと、m,nに拡張ユークリッド互除法を適用して、pm+qn=1となるp,qを求 めると、x=1-pm=qnが解となる。 　同様にして、a=0,b=1の場合の解は、x=pm=1-qnである。 　この2つの特殊な場合の解が決まれば、一般のa,bについてはそれぞれをa,b倍す ればよい。よって、x=a(qn)+b(pm)が解（の1つ）である。 [証明] [1]解の存在性を示す。 　A=nqとおくと、mp+nq=1より、次が成り立つ。 ・A=1-mp(=nq)≡1-mp mod m≡1 mod m ・A=nq≡0 mod n 　一方、B=mpとおくと、同様に次が成り立つ。 ・B=mp mod m≡0 mod m ・B=1-nq≡1 mod m 　よって、 x=aA+bB　←(**) とおけば、次が成り立つ。 ・x≡a mod m　（∵A=1∧B=0） ・x≡b mod n　（∵A=0∧B=1） 　これは解として、xが存在する。 [2]解の一意性を示す。 　(**)のxとは異なるyで、 ・y≡a mod m　←(***) ・y≡b mod n となるものがあったとし、y≡x mod mnとなることを示したい。 　「x≡a mod m∧x≡b mod n」と(***)を満たすyがあれば、次が成り立つ。 ・y-x≡0 mod m ・y-x≡0 mod n 　即ち、y-xはmの倍数∧nの倍数 　ここで、(m,n)=1より、y-xはm,nの最小公倍数のmnの倍数となる。 　よって、y-x≡0 mod mnなので、y≡x mod mnとなる。　□ 　この証明の過程から、 ・x≡a mod m ・x≡b mod n を満たすxの求め方がわかる。 　pm+qn=1かつp,a∈Zとなるp,qを用いて、 x=b(pm)+a(qn) と表される値のみが法mnとした解となる。 　以上を定理としてまとめておく。 [定理] (m,n)=1、m,n∈Nとする。 このとき、x≡a (mod m)かつx≡b (mod n)を満たす整数xはmnを法として、ただ1 つ存在する。 その解はx=anq+bmpである。 　これを中国人剰余定理（CRT)と呼ぶ。以後、CRTと略する。 　中国で紀元後5世紀頃に書かれた『孫子算経』という著書不明の数学書に載っ ていたのを、19世紀中頃に宣教師のA.Wylieが発見してヨーロッパに紹介したこ とから、この定理名が付いたという。 　pm+nq=1であるので、xは次のように変形できる。 x=anq+bmp =a+(b-a)pm =b+(a-b)qn 　この3つの表現のうち、状況に応じて好きなものを使えばよい。例えば、p,qの 一方しか求めないときは後者の2つが適しているだろう。 ■0x04.) CRTの練習問題 ○問1 　次の連立合同方程式を解け。 ・x≡3 mod 5 ・x≡5 mod 7 [方針]まず素朴な形の連立合同式の問題である。ポイントは法が互いに素かどう かを調べ、素であればCRTを使えるということである。 　このような簡単な問題をたくさん解いてCRTに慣れておくと、今後の話がわか りやすいと思う。 [解答](5,7)=1より、CRTが使える。 　5p+7q=1を満たす(p,q)の代表として、(p,q)=(3,-2)を取る。これは拡張ユーク リッド互除法を使うまでもなく、すぐに計算できる。 　CRTより、x=anq+bmp=3・7・(-2)+5・5・3=-42+75≡33 mod 35　□ ○問2 　3で割ると1余り、5で割ると3余り、7で割ると4余る正の整数のうち最小のもの を求めよ。 [方針]『孫子算経』に載っている問題を現代風にしたバージョンである。 　素朴に解く方法、CRTを積極的に使う方法、エレガントな方法など、解法は色々 ある。ここではいくつかを紹介する。 [解答]（素朴に解く方法） 　求める数がNとすると、次が成り立つ。 N=3x+1=5y+3=7z+4 (x,y,z∈Z) 　即ち、次が成り立つ。 ・3x+1=5y+3 ・5y+3=7z+4 ・3x-5y=2　←① ・5y-7z=1　←② 　①を満たす(x,y)の1つは(x,y)=(4,2)である。 　一般解は(x,y)=(5m+4,3m+2) (m∈Z) 　y=3m+2を②に代入すると、 5(3m+2)-7z=1 -7z=-15m-9 z=(15m+9)/7 z=(1+2m)+(m+2)/7 　z∈Zより、m+2=7n (n∈Z) 　よって、m=7n-2 　このmをx,y,zに代入すると、次のようになる。 ・x=5m+4=5(7n-2)+4=35n-6 ・y=3m+2=3(7n-2)+2=21n-4 ・z=(2m+1)+(m+2)/7=2(7n-2)+1=15n-3 　よって、N=3(35n-6)+1=105n-17 　n=1のとき、Nは正の整数で最小である。 　したがって、N=105・1-17=88　□ [別解]（エレガントな方法） ・N=3x+1 ・N=5y+3 ・N=7z+4 　両辺に17を足すと次のようになる。 ・N+17=3x+18=3(x+6) ・N+17=5y+20=5(y+4) ・N+17=7z+21=7(z+3) 　これより、N+17は3・5・7の倍数である。 　即ち、N+17=3・5・7m (m∈Z)である。 　m=1のとき、Nは最小である。 　よって、N+17=105なので、N=88である。　□ [別解]（『孫子算経』の解答の現代風バージョン） 　求める数をNとし、Nを3,5,7で割ったときの商をそれぞれx,y,z、余りをそれぞ れa,b,cとする。 ・N=3x+a　←① ・N=5y+b　←② ・N=7z+c　←③ 　①×70+②×21+③×15を考えて、各々の両辺を足し合わせる。 70N+21N+15N=210x+105y+105z+70a+21b+15c 106N=105(2x+y+z)+(70a+21b+15c) N=(70a+21b+15c)+105(2x+y+z-N) 　題意より、a=1,b=3,c=4であるため、次が得られる。 N =(70a+21b+15c)+105(2x+y+z-N) =(70・1+21・3+15・4)+105(2x+y+z-N) =(70+63+60)+105(2x+y+z-N) =193+105(2x+y+z-N) 　2x+y+z-N∈Zであり、Nを最小の正数にするためのは2x+y+z-N=-1のときである。 　よって、N=193-105=88である。　□ [別解]（CRTを用いる方法） ・x≡1 mod 3　←① ・x≡3 mod 5　←② ・x≡4 mod 7　←③ 　(3,5)=1より、①②に対してCRTが使える。 　3p+5q=1を満たす(p,q)の代表として、(p,q)=(-3,2)を取る。 　CRTより、x=anq+bmp=1・5・2+3・3・(-3)=10-27=-17≡13 mod 15 ・x≡13 mod 15　←④ 　(7,15)=1より、③④に対してCRTが使える。 　7r+15s=1を満たす(r,s)の代表として、(r,s)=(-2,1)を取る。 　CRTより、x=ans+bmr=13・7・(-2)+1・15・4=-182+60=-122≡88 mod 105 　ゆえに、正の整数∧最小の値は88である。　□ ○問3 　ある本を読むのに1日5ページずつ読むと4ページ残り、7ページずつ読むと5ペ ージ残り、9ページずつ読むと6ページ残るという。この本は何ページあるか？た だし、この本は200ページ以下とする。 [方針]これは中学入試問題である。 　題意は次の連立合同方程式を求める問題と同じである。 ・x≡4 mod 5　←① ・x≡5 mod 7　←② ・x≡6 mod 9　←③ 　ただし、1≦x≦200とする。 　すでにCRTを知っているので、xに制限が付かないと、答えとなるページが無限 に存在することがわかる。5・7・9=315なので、この制限が314(=315-1)であって も、ただ1つの答えが出るはずということもわかる。 　この連立合同方程式は3つの合同方程式を持つが、①〜③のそれぞれの法は互 いに素なのでCRTを2回繰り返せばよい。以上のことを踏まえて解答を考えてみる。 [解答]まず①②の連立合同方程式を解く。 　①と②は互いに素なので、5p+7q=1を満たす(p,q)の代表として(p,q)=(3,-2)を 取る。 　よって、CRTより、x=anq+bmp=4・7・(-2)+5・5・3≡19 mod 35 　したがって、「①∧②」⇔「x≡19 mod 35」 　次に、次の合同方程式を考える。 ・x≡19 mod 35　←④ ・x≡6 mod 9　←③ 　④と③は互いに素なので、35r+9s=1を満たす(r,s)の代表として(r,s)=(-1,4)を 取る。 　よって、CRTより、x=ans+bmr=19・9・4+6・35・(-1)=684-210=474≡159 mod 315 　したがって、「①∧②∧③」⇔「x≡159 mod 315」 　ゆえに、本は159ページである。　□ ○問4 　11で割ると小数第2位が3になり、13で割ると小数第1位が6になる整数を考える。 　このうち、最も小さい自然数はいくつか？ 　また、2番目に小さい自然数との差はいくつか？ [方針]これも中学入試問題の1つである。 　自然数を11で割った結果における、余りは多くても11パターンある。即ち、 「（余り）/（割る数）」の値も最大11パターンある。 　11パターンであれば、すべて列挙してもそれほど手間ではない。すべて列挙し たことで何か手掛かりがあることを期待してみる。 [解答] [1]自然数を11で割ると、次のようになる。 ・ 1÷11=0.0909… ・ 2÷11=0.1818… ・ 3÷11=0.2727… ・ 4÷11=0.3636… ・ 5÷11=0.4545… ・ 6÷11=0.5454… ・ 7÷11=0.6363…　←11で割ると小数第2位が3になるもの ・ 8÷11=0.7272… ・ 9÷11=0.8181… ・10÷11=0.9090… ・11÷11=1.0000… ・12÷11=(11+1)÷11=1.0909…　←小数部だけに注目すると1÷11と同じ。これが 「（余り）/（割る数）」に対応する。 　よって、11で割ると小数第2位が3になるものは「11で割って7余る数」である。 　即ち、7 mod 11　←(*) [2]同様に自然数を13で割ると、次のようになる。 ・ 1÷13 =0.0769… ・ 2÷13 =0.1538… ・ 3÷13 =0.2307… ・ 4÷13 =0.3076… ・ 5÷13 =0.3846… ・ 6÷13 =0.4615… ・ 7÷13 =0.5384… ・ 8÷13 =0.6153…　←13で割ると小数第1位が6になるもの ・ 9÷13 =0.6923…　←13で割ると小数第1位が6になるもの ・10÷13 =0.7692… ・11÷13 =0.8461… ・12÷13 =0.8461… ・13÷13 =1.0000… 　よって、13で割ると小数第1位が6になるものは「13で割って8,9余る数」であ る。 　即ち、8,9 mod 13　←(**) 　以上より、次の2つの連立合同方程式を解けばよい。 ・x≡7 mod 11　　・x≡7 mod 11 ・x≡8 mod 13　　・x≡9 mod 13 　CRTで求めてもよいが、ここでは143以下なのですべて列挙して調べてみる。 　11で割って7余る数で143以下のものは次の通りである。 7,18,29,40,51,62,73,84,95,106,117,128,139 　このうちで、13で割って8余るのは73、9余るのは139である。 　ゆえに、題意を満たす最も小さいものは73である。 　2番目に小さい139との差は139-73=66である。　□ ■0x05.) 一般の中国人剰余定理 　3個以上の合同方程式であっても、CRTを繰り返せばよいことはすでに言及済み である。ここでは合同方程式の個数に対して一般化を施したCRTを考える。 [定理] m1,m2,…,m_r∈Nで、どの2つも互いに素とする。 任意の整数a1,a2,…,a_rに対して、連立方程式 ・x=a1 mod m1 ・x=a2 mod m2 … ・x=a_r mod m_r を満たす整数xはm1m2…m_rを法としてただ1つ存在する。 M_i=M/m_i y_i=(M_i)^(-1) (mod m_i) i=1,…,r とすると、 その解はx≡Σ[i=1:r]a_i(M_i・y_i) (mod M)である。 [方針]ここで、M_iとy_iをかけると、法によって0または1と一致する。 　法がm_iのときだけ1になり、それ以外のときだけ0になる。 　即ち、次が成り立つ。 ・M_i・y_i≡1 (mod m_i) ・M_i・y_i≡0 (mod m_j),j≠i 　これを利用すると、aM_i・y_iは次のようになる（合同式の両辺にaを掛けただ け）。 ・aM_i・y_i≡a (mod m_i) ・aM_i・y_i≡0 (mod m_j),j≠i [証明][1]解の存在を示す。 x:=M1y1a1+…+M_r・y_r・a_rとおくと、 x =M1y1a1+…+M_r・y_r・a_r ≡0・a_1+…+0・a_(i-1)+1・a_i+0・a_(i+1)+…+0・a_r (mod m_i)　（∵考察の結果） ≡1・a_i (mod m_i) ≡a_i (mod m_i) [2]解の一意性を示す。 x,x'：2つの解 ・x≡x' (mod m_1) ・… ・x≡x' (mod m_r) x-x'はm_1,…,m_rの倍数である。 よって、x-x'はLCM(m1,…,m_r)の倍数である。 (m_1,…,m_r)=1（m_1,…,m_rは互いに素）より、x-x'はm_1・…・m_r(=M)の倍数 である。 x-x'≡0 (mod M) ∴x≡x' (mod M)　□ 　一般のCRTの解き方も重要だが、「mod m1m2…m_rで決まる数aとmod n_i(i=1,… ,r)で決まるk個の数a_iの組が1対1対応する」ことも重要である。 　即ち、 「a mod m1m2…m_r」 ⇔ 「連立合同方程式 ・a1 mod m1 ・a2 mod m2 … ・a_r mod m_r」 　上から下への写像は単にaとmod m_iに対応させるだけである。 　逆に下から上への写像は一般のCRTそのものである。 　この対応は加減乗算による関係もそのまま対応付く。即ち、環の同型写像であ る。 ■0x06.) CRTのxの係数が1でない場合 　次の連立合同方程式を解きたいとする。 ・a1x≡b1 mod m1 ・a2x≡b2 mod m2 … ・a_r・x≡b_r mod m_r 　法と係数が互いに素であるかどうかで場合分けが生じる。 [1](a_i,m_i)=1であれば、ただ1つの解がある。逆元(a_i)^(-1)を計算して、両辺 にかければ係数が消える。 [2](a_i,m_i)=d_i(＞1)であれば、m_iを法としてd個の解がある。ここでは合同 方程式を単純化するのを目的とするので、法を含めて両辺をd_iで割ればよい。 　後はそれぞれの合同方程式の法が互いに素であればCRTが使える。 例：次の連立方程式を解く。 ・5x≡7 mod 11 ・6x≡10 mod 19 　(5,11)=1,(6,19)=1より、[1]の場合を使えばよい。 ・x≡5^(-1)・7 mod 11 ・x≡6^(-1)・10 mod 19 ・x≡63 mod 11　（∵5^(-1)=9） ・x≡-3・10 mod 19　（∵6^(-1)=-3） ・x≡8 mod 11 ・x≡8 mod 19 　(11,19)=1より、CRTを使える。 　11p+19q=1を満たす(p,q)の代表として、(p,q)=(7,-4)を取る。 　x=anq+bmp=8・19・(-4)+8・11・7=-608+616≡8 mod 209　□ ■0x07.) 一般のCRTの練習問題 ○問1 　次の連立合同方程式を求めよ。 ・x≡1 mod 3 ・x≡2 mod 5 ・x≡3 mod 7 [方針]CRTを2回使っても求めることができるが、ここでは一般のCRTを使うこと にする。 [解答]m1=3,m2=5,m3=7は互いに素なので一般のCRTが使える。 ・M=m1m2m3=105 ・M1=M/m1=m2m3=35 ・M2=M/m2=m1m3=21 ・N3=M/m3=m1m2=15 [1] y1=M1^(-1) mod m1≡35^(-1) mod 3≡2^(-1) mod 3≡2 mod 3 M1y1=35・2=70 [2] y2=M2^(-1) mod m2≡21^(-1) mod 5≡1 mod 5 M2y2=21・1=21 [3] y3=M3^(-1) mod m3≡15^(-1) mod 7≡1 mod 7 M3y3=15・1=15 　したがって、解xは次の通りである。 x=1・70+2・21+3・15=70+42+45 mod 105≡52 mod 105　□ 　文字がたくさん登場してわかりにくいかもしれないが、M_i・y_iに注目すると わかりやすい。 　このM_i・y_i (i=1,2,3)には次の関係が成り立っている。 ・M1y1≡1 mod 3 ・M1y1≡0 mod 5 ・M1y1≡0 mod 7 かつ ・M2y2≡0 mod 3 ・M2y2≡1 mod 5 ・M2y2≡0 mod 7 かつ ・M3y3≡0 mod 3 ・M3y3≡0 mod 5 ・M3y3≡1 mod 7 　が成り立つため、解xも次が成り立つ。 ・x=1・1+2・0+3・0 mod 3 ・x=1・0+2・1+3・0 mod 5 ・x=1・0+2・0+3・1 mod 7 ■0x08.) CRTによる1次合同方程式の解法 　1次合同方程式 13x≡17 (mod 105)　←(*) を解くためには、13c≡1 (mod 105)を満たすcを見つけて、(*)の両辺にcを掛け ればよい。 また、1次不定方程式13x+105y=17を解けばよい。 　ここでは(*)を簡単な1次合同方程式の連立方程式に変換して、それらから解を 求めることができる。 　105=3・5・7より、次の連立方程式を得る。 ・13x≡17 (mod 3) ・13x≡17 (mod 5) ・13x≡17 (mod 7) 　CRTを利用するために、法が互いに素であることの他に、xの係数が1になるよ うに変換する。 ・x≡2 (mod 3) ・3x≡2 (mod 5) ・-x≡3 (mod 7) ・x≡2 (mod 3) ・x≡4 (mod 5) ・x≡-3 (mod 7) ・x≡2 (mod 3) ・x≡4 (mod 5) ・x≡4 (mod 7) 　これでCRTが使える。 m1=3,m2=5,m3=7 a1=2,a2=4,a3=5 M=M1・M2・M3=105 M1=M/m1=m2・m3=35,M2=M/m2=m1・m3=21,M3=M/m3=m1・m2=15 　次に、y_i,i=1,2,3を求める。 y1 =M1^(-1) (mod m1) =35^(-1) (mod 3) =2^(-1) (mod 3) =2 (mod 3) y2 =M2^(-1) (mod m2) =21^(-1) (mod 5) =1 (mod 5) y3 =M3^(-1) (mod m3) =15^(-1) (mod 7) =1 (mod 7) 　M_i,y_iが計算できたので、M_i・y_iを求める。 M1・y1=35・2=70　←mod 3のときに1、mod 5あるいは7のときに0であることに注目。 M2・y2=21・1=21　←mod 5のときに1、mod 3あるいは7のときに0であることに注目。 M3・y3=15・1=15　←mod 7のときに1、mod 3あるいは5のときに0であることに注目。 　よって、xは次のように計算できる。 x ≡a1M1y1+a2M2y2+a3M3y3 (mod M) ≡2・70+4・21+4・15 (mod 105)　←mod 3なら2・70、mod 5なら4・21、mod 7な ら4・15のところだけが残ることに注目。 ≡140+84+60 (mod 105) ≡35-21+60 (mod 105) ≡74 (mod 105)　◇ ■0x09.) CRTを用いたRSA暗号の復号処理の高速化 　RSAの復号アルゴリズムは次のように計算することは、すでにWB34で解説済み である。 1：暗号文c、秘密鍵sk=d、公開鍵pk=(N,e)を入力とする。 2：次の計算を行い、その計算結果を平文として出力する。 c^d (mod N)　←(*) 　ここではCRTを利用して、この復号の計算の効率化した方式がQuisquaterとCou vreurによって提案されている[QC84]。 　この効率化が施された復号アルゴリズムは次の通りである。CRTのアルゴリズ ムの違いにより、復号アルゴリズムの処理に少し違いが出てくる（本質的にはほ とんど変わらない）。 ○バージョン1 1：暗号文c、秘密鍵sk=d、公開鍵pk=(N,e)を入力とする。 2：次のC_p,C_qを計算する。 ・C_p=C mod p ・C_q=C mod q 3：次のM_p,M_qを計算する。 ・M_p=(C_p)^(d_p) mod p ・M_q=(C_q)^(d_q) mod q 　ただし、d_p=d mod (p-1)、d_q=d mod (q-1)とする。 4：次のVを計算する。 V=v(M_q-M_p) mod q 　ただし、v=p^(-1) mod qである。 　もし、値が負の数であればqの倍数を加えて、0≦V＜qとなるようにする。 5：Vp+M_pを計算して、出力する。 ○バージョン2 　今回の記事ではこちらのCRTのアルゴリズムを取り上げているので、こちらの 方がわかりやすいかもしれない。 1：暗号文c、秘密鍵sk=d、公開鍵pk=(N,e)を入力とする。 2：次を計算する。 ・d_p=d mod (p-1) ・d_q=d mod (q-1) ・P=qq' mod N　ただし、qq'≡1 (mod p) ・Q=pp' mod N　ただし、pp'≡1 (mod q) 3：暗号文cに対して、次のC_p,C_qを計算する。 ・C_p=C mod p ・C_q=C mod q 4：次のM_p,M_qを計算する。　←(**) ・M_p=(C_p)^(d_p) mod p ・M_q=(C_q)^(d_q) mod q 5：P・M_p＋Q・M_q mod Nを計算して出力する。 ○バージョン2のアルゴリズムの解説 　ステップ2〜3はcがなくても計算できるので、事前計算が可能である。 　ステップ4では、d_pやd_qによるべき乗剰余演算を行っている。ここが一番大 変な計算である。WB35で紹介したアルゴリズム（バイナリ法という）を使えば、 単純に計算するよりは効率がよい。 　len(・)はビット長を意味するものとする。 　(*)はd乗し、Nを法とするべき乗剰余演算であり、その計算量はO(len(d)・(len (N)^2))である。 　また、len(p)〜len(q)〜len(N)/2、len(d_p)〜len(d_q)〜len(d)/2が成り立つ。 よって、(**)の計算量は次のように計算できる。 len(d_p)・len(p)^2+len(d_q)・len(q)^2 =(len(d)/2)(len(N)/2)^2+(len(d)/2)・(len(N)/2)^2 =(len(d)・(len(N)^2))/4 　よって、(**)の計算量は(*)の計算量の4分の1になった。ステップ5はステップ 2から見ればほとんど無視できるが、それらを考慮しても、(**)の計算量は(*)の 計算量の約4分の1になる。 　このCRTを用いるアプローチはNの素因数であるp,qがわかる場合でしか使えな い。つまり、復号アルゴリズムでのみ使用できるわけである。 ■0x0A.) CRTと剰余表現 　m1,m2,…,m_rを互いに素な正の整数とし、(m_i)^2はコンピュータの扱える整数 演算で正確に計算できるものとする。 　このとき、 n＜m1・m2・…・m_r を満たす任意の正の整数は、次の集合によって完全に決定される。 ・a1=n mod m1 ・a2=n mod m2 ・… ・a_r=n mod m_r 　このとき、表現n=[a1,a2,…,a_r]はnの（剰余）基底(m1,m2,…,m_r)を用いた 剰余表現と呼ぶ。 　実際には、m1,m2,…,m_rは互いに異なる素数が選ばれるものとすれば、CRTが 整数の別表現として剰余表現があることを示唆していることがわかる。 ○例 　素数の集合を用いて、(m1,m2,…,m_r)=(191,193,197,199)とする。 　このとき、m1・m2・…・m_r=191・193・197・199=1445140189となる。この144 5140189よりも小さい任意の整数nは基底(191,193,197,199)に関する剰余表現を 持つ。 　ここで、n=1000000000の基底(191,193,197,199)を用いた剰余表現を調べる。 ・1000000000 mod 191=18 ・1000000000 mod 193=29 ・1000000000 mod 197=26 ・1000000000 mod 190=125 　よって、n=1000000000の基底(191,193,197,199)を用いた剰余表現は[18,29,26 ,125]である。 ○剰余表現を用いた整数の演算 　剰余表現を用いると、コンピュータで整数計算が行える最大値を超えるような 大きな整数の演算が簡単になる。その際、次の定理を用いる。 [定理]剰余基底(m1,m2,…,m_r)を用いた剰余表現k=[a1,a2,…,a_r]およびn=[b1, b2,…,b_r]が与えられたときに、m=m1・m2・…・m_rとおくと、次が成り立つ。 (1) k+n mod m=[a1+b1 mod m1,a2+b2 mod m2,…,a_r+b_r mod m_r] (2) kn mod m=[a1・b1 mod m1,a2・b2 mod m2,…,a_r・b_r mod m_r] (3) k^j mod m=[a1^j mod m1,a2^j mod m2,…,(a_r)^j mod m_r] [証明]a_i=k mod m_iかつb_i=n mod m_iであるとき、次が成り立つ。 ・a_i+b_i≡k+n mod m_i ・a_i・b_i≡kn mod m_i ・(a_i)^j≡k^j mod m_i 　よって、題意が成り立つ。　□ [系]剰余基底(m1,m2,…,m_r)を用いた剰余表現k=[a1,a2,…,a_r]およびn=[b1,b2 ,…,b_r]が与えられたときに、m=m1・m2・…・m_rとおくと、次が成り立つ。 (1)k+n＜mのとき、次が成り立つ。 k+n=[a1+b1 mod m1,a2+b2 mod m2,…,a_r+b_r mod m_r] (2)kn＜mのとき、次が成り立つ。 kn=[a1・b1 mod m1,a2・b2 mod m2,…,a_r・b_r mod m_r] (3)k^j＜mのとき、次が成り立つ。 k^j=[a1^j mod m1,a2^j mod m2,…,(a_r)^j mod m_r] 　コンピュータで整数計算が行える最大値を65535（＝256・256-1）とすると、 基数b=256による表示が自然である。 　このとき、k=Σ[i=0;20]a_i・b^i、n=Σ[i=0;20]c_i・b_iとしたときの計算の 手間を考える。 　素朴に基数b=256としたとき、積knの計算はkの展開の各項とnの展開の各項と の積になる。つまり、21^2=441回の乗算と、多くの加算と繰り上がりが必要にな る。 　一方、剰余基底(m1,m2,…,m_r)=(2,3,5,…,251)（256以下のすべての素数たち ）を用いた剰余表現を用いれば、54回の乗算を必要とする。そして、加算と繰り 上がりもない。 　したがって、同じ積を計算するにしても、剰余表現を用いた方が乗算回数がか なり少ないことがわかる。 ■0x0B.) 参考文献 ・『ガウスとオイラーの整数論』 ・『応用代数学入門』 ・『初等整数論』 ・『高校・大学生のための整数の理論と演習』 ・『暗号理論入門　暗号アルゴリズム、署名と認証、その数学的基礎』 ・[QC82]"Fast decipherment algorithm for RSA public-key cryptosystem" x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第3章: お知らせ --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ○Wizard Bible（http://wizardbible.org/）では随時、執筆ライターを募集して います。 　扱う内容のテーマは広義での「under ground」です。例えばハッキングやセキ ュリティからピッキングなどと幅広い内容を考えています。また特殊な職業や趣 味の解説などでも構いません。 　一回きりでも構いません。また必ず毎回連載する義務もありませんので、でき る範囲で構いません。気軽に声をかけてください。 ○Kenji AikoさんがQ&Aを作ってくれました。初めて参加する人でもわかりやすく 書かれていますので、参考にしてください。 http://wizardbible.org/wbQandA.html ○Wizard Bibleに参加希望の方は気軽にメール（ipusiron@gmail.com）ください。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ---- 第4章: 著者プロフィール --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■unya ●Job: ネットワークエンジニア ●Web: http://routehack.org/ ●Mail: unya@routehack.org ●Comment: 　8月、9月とプライベートで色々とあって、ようやく落ち着いてきたと思ったら、 今度は空き巣に窓ガラスを割られました。お巡りさん曰く、手袋痕しか採取でき なかったそうなので、次回に備えてバッチリと証拠を残せるようなシステムを導 入しようと思案中です。オススメなシステムがあったら教えてください。では。 ■IPUSIRON ●Job: プログラマー ●Web: http://akademeia.info ●Mail: ipusiron@gmail.com ●Comment: 　伊豆にデータハウス主催の新しい博物館・まぼろし博覧会ができました。先々 週に私も覗きに行ってきました。 http://maboroshi.pandora.nu/ 　怪しい少年少女博物館や猫の博物館も近くになるので、まとめて見学するのも 可能です。